hdu1874畅通工程续 (dijkstra)
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>int map[205][205],node[205],s[205],n,sn,INF=10000000;void setfisrt(){ for(int i=0;i<n;i++) { s[i]=0; node[i]=INF; for(int j=0;j<n;j++) map[i][j]=INF; }}int dijkstra(int en){ int min,ten=en; s[en]=1; node[en]=0; for(int k=2;k<=n;k++) { min=INF; for(int i=0;i<n;i++) if(s[i]==0) { if(node[i]>map[ten][i]+node[ten]) node[i]=map[ten][i]+node[ten]; if(min>node[i]) { min=node[i]; en=i; } } s[en]=1; ten=en; } if(node[sn]==INF) return -1; return node[sn];}int main(){ int m,en,a,b,p; while(scanf("%d%d",&n,&m)>0) { setfisrt(); while(m--) { scanf("%d%d%d",&a,&b,&p); if(p<map[a][b]) map[a][b]=map[b][a]=p; } scanf("%d%d",&sn,&en); printf("%d\n",dijkstra(en)); }}
