lightoj1002

CODE

#include <bits/stdc++.h>
#define CL(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 0x3f3f3f3f;
int n,s,m,t;
int g[505][505];
int dis[505],vis[505];
int main()
{
        scanf("%d",&t);
        for(int nCase=1;nCase<=t;nCase++)
        {
                cout << "Case "<<nCase<<":"<<endl;
                CL(g,0x3f);
                CL(dis,0x3f);
                CL(vis,0);
                scanf("%d %d",&n,&m);
                while(m--)
                {
                        int u,v,w;
                        scanf("%d %d %d",&u,&v,&w);
                        g[u][v]=g[v][u]=min(w,g[u][v]);
                }
                scanf("%d",&s);
                //dij
                dis[s]=0;
                for(int i=0;i<n;i++)
                {
                        int mi=INF,p;
                        for(int j=0;j<n;j++)
                                if(!vis[j]&&dis[j]<mi){mi=dis[j];p=j;}
                        vis[p]=1;
                        for(int j=0;j<n;j++)
                        {
                                if(vis[j])continue;
                                if(g[p][j]!=INF)        dis[j]=min(dis[j],max(g[p][j],dis[p]));
                        }
                }
                for(int i=0;i<n;i++)
                {
                        if(dis[i]!=INF)printf("%d\n",dis[i]);
                        else printf("Impossible\n");
                }
        }

        return 0;
}