1 //dijkstra 2 #include <cstdio> 3 #define min(x,y) (x<y)?x:y 4 const int max_e=10005; 5 const int max_v=105; 6 const int INF=0x3f3f3f3f; 7 int cost[max_v][max_v]; 8 bool vis[max_v]; 9 int d[max_v];10 int V,E;11 void dijkstra(int s)12 {13     for(int i=1;i<=V;i++)14     {15         d[i]=cost[s][i];16         vis[i]=false;17     }18     d[s]=0;19     while(true)20     {21         int v=-1;22         for(int i=1;i<=V;i++)23         {24             if(!vis[i] && (v == -1 || d[i]<d[v]))25                 v=i;26         }27         if(v==-1) break;28         vis[v]=true;29         for(int i=1;i<=V;i++)30         {31             d[i]=min(d[i], d[v]+cost[v][i]);32 33         }34     }35 }36 int main()37 {38     while(~scanf("%d%d",&V,&E))39     {40         if(!V && !E) break;41         int from,to,co;42         for(int i=1;i<=V;i++)43         {44             for(int j=1;j<=V;j++)45             {46                 if(i==j) cost[i][j]=0;47                 cost[i][j]=INF;48             }49         }50         for(int i=0;i<E;i++)51         {52             scanf("%d%d%d",&from,&to,&co);53             cost[from][to]=cost[to][from]=co;54         }55         dijkstra(1);56         printf("%d\n",d[V]);57     }58     return 0;59 }

 1 //floyd 2 #include <cstdio> 3 #define min(x,y) (x<y)?x:y 4 const int max_e=10005; 5 const int max_v=105; 6 const int INF=0x3f3f3f3f; 7  8 int d[max_v][max_v]; 9 int V,E;10 11 void Floyd()12 {13     for(int k=1;k<=V;k++)14     {15         for(int i=1;i<=V;i++)16         {17             for(int j=1;j<=V;j++)18             {19                 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);20             }21         }22     }23 }24 int main()25 {26 27     while(~scanf("%d%d",&V,&E))28     {29         if(!V && !E) break;30         int from,to,cost;31         for(int i=1;i<=V;i++)32         {33             for(int j=1;j<=V;j++)34             {35                 if(i==j)36                     d[i][j]=0;37                 else38                     d[i][j]=d[j][i]=INF;39             }40         }41         for(int i=0;i<E;i++)42         {43             scanf("%d%d%d",&from,&to,&cost);44             d[from][to]=d[to][from]=cost;45         }46         Floyd();47         printf("%d\n",d[1][V]);48     }49     return 0;50 }

 1 #include <cstdio> 2 #define min(x,y) (x<y)?x:y 3 #define max(x,y) (x>y)?x:y 4 const int INF=0x3f3f3f3f; 5 const int max_v=1005; 6 int E,V,D,eend; 7 int max_num;//剪枝 8 int cost[max_v][max_v]; 9 bool vis[max_v];10 int s[max_v],d[max_v];11 void dijkstra(int s)12 {13     for(int i=0;i<=max_num;i++)14     {15         d[i]=cost[s][i];16         vis[i]=false;17     }18     d[s]=0;19     while(true)20     {21         int v=-1;22         for(int i=0;i<=max_num;i++)23         {24             if(!vis[i] && (v==-1 || d[i]<d[v]))25                 v=i;26         }27         if(v==-1) break;28         vis[v]=true;29         for(int i=0;i<=max_num;i++)30         {31             d[i]=min(d[i],d[v]+cost[v][i]);32         }33 34     }35 36 }37 int main()38 {39     while(~scanf("%d%d%d",&E,&V,&D))40     {41         //init42         max_num=0;43         for(int i=0;i<=max_v-5;i++)44             for(int j=0;j<=max_v-5;j++)45             {46                 if(i==j) cost[i][j]=0;47                 else cost[i][j]=INF;48             }49         int a,b,time;50         for(int i=0;i<E;i++)51         {52             scanf("%d%d%d",&a,&b,&time);53             max_num=max(max_num,a);54             max_num=max(max_num,b);55             if(cost[a][b]>time) cost[a][b]=cost[b][a]=time;56         }57 58         for(int i=0;i<V;i++)59         {60             scanf("%d",&s[i]);61             cost[0][s[i]]=cost[s[i]][0]=0;62         }63 64         dijkstra(0);65         int ans=INF;66         for(int i=0;i<D;i++)67         {68             scanf("%d",&eend);69             ans=min(ans,d[eend]);70         }71         printf("%d\n",ans);72     }73     return 0;74 }

 1 #include <cstdio> 2 #include <map> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 const int ssize=34; 8 int n,cnt; 9 char start[ssize],over[ssize];10 map<string,int>mmap;11 const int maxn=155;12 const int INF=0x3f3f3f3f;13 int cost[maxn][maxn];14 int d[maxn];15 bool vis[maxn];16 void init()17 {18     mmap.clear();//***19     for(int i=1;i<=maxn-5;i++)20     {21         for(int j=1;j<=maxn-5;j++)22         {23             if(i==j) cost[i][j]=0;24             else cost[i][j]=INF;25         }26     }27 }28 void dijkstra(int s)29 {30     for(int i=1;i<cnt;i++)31     {32         d[i]=cost[s][i];33         vis[i]=false;34     }35     d[s]=0;36     while(true)37     {38         int v=-1;39         for(int i=1;i<cnt;i++)40         {41             if(!vis[i] && (v==-1 || d[i] < d[v]))42                 v=i;43         }44         if(v==-1) break;45         vis[v]=true;46         for(int i=1;i<cnt;i++)47         {48             d[i]=min(d[i],d[v]+cost[v][i]);49         }50     }51 }52 53 int main()54 {55 56     while(~scanf("%d",&n))57     {58         if(n==-1) break;59         init();60         bool same=false;61         scanf("%s%s",start,over);62         if(!strcmp(start,over)) same=true;63         mmap[start]=1;mmap[over]=2;64 65         char s[ssize],o[ssize];66         int dis;67         cnt=3;68         for(int i=0;i<n;i++)69         {70             scanf("%s%s%d",s,o,&dis);71 72             if(!mmap[s]) mmap[s]=cnt++;73             if(!mmap[o]) mmap[o]=cnt++;74             cost[ mmap[s] ][ mmap[o] ]=cost[ mmap[o] ][ mmap[s] ]= min (cost[ mmap[s] ][ mmap[o] ] , dis);75         }76 77         if(same==true) {printf("0\n");continue;}78         dijkstra(1);79         if(d[2]!=INF)80             printf("%d\n",d[2]);81         else82             printf("-1\n");83     }84     return 0;85 }