最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 36086 Accepted Submission(s): 15700
Problem Description
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的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条商店到赛场的路线。
输入保证至少存在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
Source
解题思路:
裸裸的Dijkstra的模板题,什么变化都没有,直接上就好了。
代码:
# include<cstdio> # include<iostream> using namespace std; # define MAX 100+4 # define inf 99999999 int edge[MAX][MAX]; int dis[MAX]; int book[MAX]; int n,m; int u,v; void init() { for ( int i = 1;i <= n;i++ ) { for ( int j = 1;j <= n;j++ ) { if ( i==j ) { edge[i][j] = 0; } else { edge[i][j] = inf; } } } } void input() { for ( int i = 1;i <= m;i++ ) { int t1,t2,t3; cin>>t1>>t2>>t3; edge[t1][t2] = edge[t2][t1] = t3; } } void Dijkstra() { for ( int i = 1;i <= n;i++ ) { dis[i] = edge[1][i]; book[i] = 0; } dis[1] = 0; book[1] = 1; int _min; for ( int i = 1;i <= n-1;i++ ) { _min = inf; for ( int j = 1;j <= n;j++ ) { if ( book[j]==0&&dis[j] < _min ) { _min = dis[j]; u = j; } } book[u] = 1; for ( v = 1;v <= n;v++ ) { if ( book[v] == 0 && dis[v] > dis[u]+edge[u][v] ) { dis[v] = dis[u] + edge[u][v]; } } } } int main(void) { while ( cin>>n>>m ) { if ( n==0&&m==0 ) break; init(); input(); Dijkstra(); printf("%d\n",dis[n]); } }
由于刚学SPFA,故用SPFA来解决下,,,因为SPFA的复杂度是O(E),而Dijkstra的复杂度是O(ElogV),SPFA还是相当快的。。。用SPFA的时候,queue可以用STL中的,也可以用数组来模拟,两个差不多,习惯那个用哪个吧。。。。有关SPFA的详细介绍,在后面的blog中还会陆续更新的。。。
# include<cstdio> # include<iostream> # include<queue> using namespace std; # define MAX 100+4 # define inf 99999999 int edge[MAX][MAX]; int dis[MAX]; int book[MAX]; int n,m; int ans; queue<int>q; void init() { for ( int i = 1;i <= n;i++ ) { for ( int j = 1;j <= n;j++ ) { if ( i==j ) { edge[i][j] = 0; } else { edge[i][j] = inf; } } } } void input() { for ( int i = 1;i <= m;i++ ) { int t1,t2,t3; cin>>t1>>t2>>t3; edge[t1][t2] = edge[t2][t1] = t3; } } int spfa ( int x ) { for ( int i = 1;i <= n;i++ ) { book[i] = 0; dis[i] = inf; } q.push(x); book[x] = 1; dis[x] = 0; while ( !q.empty() ) { int cur = q.front(); q.pop(); for ( int i = 1;i <= n;i++ ) { if ( dis[i] > dis[cur] + edge[cur][i] ) { dis[i] = dis[cur] + edge[cur][i]; if ( book[i] == 0 ) { book[i] = 1; q.push(i); } } } book[cur] = 0; } return dis[n]; } int main(void) { while ( cin>>n>>m ) { if ( n==0&&m==0 ) break; init(); input(); ans = spfa( 1 ); printf("%d\n",ans); } return 0; }