lightoj1019

CODE

#include <iostream>
#include <cstring>
int nCase;
#define CL(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf = 0x3f3f3f3f;
int n,m,g[105][105],d[105],vis[105];
void dij()
{
        d[1]=0;
        for(int i=0;i<n;i++)
        {
                int mi=inf,index=0;
                for(int j=1;j<=n;j++)
                        if(!vis[j]&&d[j]<mi){mi=d[j];index=j;}
                vis[index]=1;
                for(int j=1;j<=n;j++)
                {
                        if(!vis[j]&&g[index][j]+d[index]<d[j])
                                d[j]=g[index][j]+d[index];
                }
        }
}


int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                CL(d,0x3f);
                CL(vis,0);
                CL(g,0x3f);
                cin >> n>>m;
                for(int i=0;i<m;i++)
                {
                        int u,v,w;
                        cin >> u >> v >> w;
                        if(w<g[u][v])g[v][u]=g[u][v]=w;
                }
                dij();
                cout <<"Case "<<++nCase<<": ";
                if(d[n]==inf) cout <<"Impossible"<<endl;
                else cout << d[n]<<endl;
        }

        return 0;
}