lightoj 1002

最短路的变形，使用spfa做。
#include<set>

#include<map>

#include<list>

#include<stack>

#include<queue>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

#define LL long long

#define INF 0x7fffffff

#define debug cout << "here" << endl

#define CLR(X, Y) memset(X, Y, sizeof X)

#define FOR(X, Y) for(int i = X;i < Y;i ++)

inline int myMin(int x, int y){return x < y ? x : y;}

inline int myMax(int x, int y){return x < y ? y : x;}

const int MAXN = 505;

int mat[MAXN][MAXN], n;

void bfs(int t){

    queue<int>Q;

    int dist[MAXN], vis[MAXN];

    CLR(dist, 1), CLR(vis, 0);

    Q.push(t), dist[t] = 0, vis[t] = 1;

    while(!Q.empty()){

        int u = Q.front();

        vis[u] = 0;

        Q.pop();

        for(int i = 0;i < n;i ++){

            if(mat[u][i] > 0){

                if(dist[i] > max(mat[u][i], dist[u])){

                    dist[i] = max(mat[u][i], dist[u]);

                    if(!vis[i]){

                        Q.push(i);

                        vis[i] = 1;

                    }

                }

            }

        }

    }

    for(int i = 0;i < n;i ++){

        if(dist[i] > 20000) printf("Impossible\n");

        else printf("%d\n", dist[i]);

    }

}

int main(int argc, char* argv[]){

    int t,  m, u, v, w;

#ifndef ONLINE_JUDGE

    freopen("in.cpp", "r", stdin);

#endif

    scanf("%d", &t);

    int tmp = t;

    while(t--){

        printf("Case %d:\n", tmp-t);

        memset(mat, 0, sizeof mat);

        scanf("%d%d", &n, &m);

        for(int i = 0;i < m;i ++){

            scanf("%d%d%d", &u, &v, &w);

            if(mat[u][v] == 0) mat[u][v] = mat[v][u] = w;

            else  mat[u][v] = mat[v][u] = min(mat[u][v], w);

        }

        scanf("%d", &m);

        bfs(m);

    }

    return 0;

}
巴特西

lightoj 1002

最新文章

热门文章
