HDU 2544

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？  Input 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。  输入保证至少存在1条商店到赛场的路线。  Output 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 Sample Input 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 Sample Output 3

2

// // Created by liyuanshuo on 2017/3/12. // /* #include <iostream> #include <limits> #include <cstring> #include <cstdio> using namespace std; const int maxn= 110; int mapp[maxn][maxn], vis[maxn], ans[maxn]; void beginInit() { fill (vis, vis+maxn, 0 ); fill (ans, ans+maxn, INT16_MAX ); for (int i = 0; i < maxn ; ++i) { for (int j = 0; j < maxn ; ++j) { mapp[i][j] = INT16_MAX; } } //memset (mapp, INT16_MAX, sizeof (mapp)); } void Dijkstra( int n, int goal ) { ans[goal] = 0; while ( true ) { int tmpv = -1; for (int i = 1; i <= n ; ++i) { if( !vis[i] && ( tmpv==-1 || ans[i]<ans[tmpv] ) ) tmpv = i; } if ( tmpv == -1 ) break; vis[tmpv] = 1; for (int j = 1 ; j <= n ; ++j) { ans[j] = min (ans[j], ans[tmpv]+mapp[tmpv][j] ); } } } int main( ) { //freopen ( "F:\\CSLeaning\\Thinking in C++\\C402\\in.in", "r", stdin ); int n, m; while ( cin>>n>>m , m+n ) { beginInit (); //int times = n; while ( m-- ) { int a, b, c; cin>>a>>b>>c; mapp[a][b] = mapp[b][a] = c; } Dijkstra (n, 1); cout<<ans[n]<<endl; } return 0; } */ #include<cstdio> #include<iostream> #define maxn 101 #define inf 99999999 using namespace std; int n,m; int mapp[maxn][maxn],vis[maxn],d[maxn]; void init() { fill(vis,vis+n+1,0); fill(d,d+n+1,inf); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) mapp[i][j]=inf; } } void dij(int s) { d[s]=0; while(1) { int v=-1; for(int i=1;i<=n;i++) if(!vis[i]&&(v==-1||d[i]<d[v])) v=i; if(v==-1) break; vis[v]=1; for(int i=1;i<=n;i++) d[i]=min(d[i],d[v]+mapp[v][i]); } } int mainF() { cin.sync_with_stdio(false); while(cin>>n>>m,n+m) { init(); while(m--) { int s,e,w; cin>>s>>e>>w; mapp[s][e]=mapp[e][s]=w; } dij(1); cout<<d[n]<<endl; } return 0; }