图论trainning-part-1 A. 最短路

A. 最短路

Time Limit: 1000ms

Memory Limit: 32768KB

64-bit integer IO format: %I64d Java class name: Main

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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

Sample Output

3

2

解题：最短路。。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 int mp[][],d[],n,m;

 bool vis[];

 void dij(){

     int i,j,theMin,index;

     for(i = ; i <= n; i++)

         d[i] = INF>>;

     d[] = ;

     memset(vis,false,sizeof(vis));

     for(i = ; i < n; i++){

         theMin = INF;

         for(j = ; j <= n; j++){

             if(!vis[j] && theMin > d[j]) theMin = d[index = j];

         }

         vis[index] = true;

         if(index == n) break;

         for(j = ; j <= n; j++){

             if(!vis[j] && d[j] > d[index]+mp[index][j])

                 d[j] = d[index] + mp[index][j];

         }

     }

 }

 int main(){

     int i,j,u,v,w;

     while(scanf("%d%d",&n,&m),n||m){

         for(i = ; i <= n; i++)

         for(j = ; j <= n; j++)

             mp[i][j] = INF;

         for(i = ; i < m; i++){

             scanf("%d%d%d",&u,&v,&w);

             mp[u][v] = mp[v][u] = w;

         }

         dij();

         printf("%d\n",d[n]);

     }

     return ;

 }

优先队列版Dijkstra

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <queue>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 #define pii pair<int,int>

 const int maxn = ;

 struct arc {

     int to,w;

 };

 int n,m;

 vector<arc>g[maxn];

 bool done[maxn];

 int d[maxn];

 priority_queue<pii,vector< pii >,greater< pii > >q;

 void dj() {

     int i,j;

     for(i = ; i <= n; i++) {

         done[i] = false;

         d[i] = INF;

     }

     d[] = ;

     while(!q.empty()) q.pop();

     q.push(make_pair(d[],));

     while(!q.empty()) {

         pii u =q.top();

         q.pop();

         int x = u.second;

         if(done[x]) continue;

         done[x] = true;

         for(i = ; i < g[x].size(); i++) {

             j = g[x][i].to;

             if(d[j] > d[x] + g[x][i].w) {

                 d[j] = d[x]+g[x][i].w;

                 q.push(make_pair(d[j],j));

             }

         }

     }

 }

 int main() {

     int i,j,u,v,w;

     while(scanf("%d%d",&n,&m),n||m) {

         for(i = ; i <= n; i++)

             g[i].clear();

         for(i = ; i < m; i++) {

             scanf("%d%d%d",&u,&v,&w);

             g[u].push_back((arc) {v,w});

             g[v].push_back((arc) {u,w});

         }

         dj();

         printf("%d\n",d[n]);

     }

     return ;

 }

Bellman—Ford算法：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <queue>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 #define pii pair<int,int>

 const int maxn = ;

 struct arc {

     int u,v,w;

 } g[maxn];

 int n,m,cnt;

 int d[maxn];

 void bf() {

     int i,j;

     for(i = ; i <= n; i++)

         d[i] = INF;

     d[] = ;

     bool flag;

     for(i = ; i < n; i++) {

         flag = true;

         for(j = ; j < cnt; j++)

             if(d[g[j].v] > d[g[j].u]+g[j].w){

                  d[g[j].v] = d[g[j].u]+g[j].w;

                  flag = false;

             }

         if(flag) break;

     }

 }

 int main() {

     int i,u,v,w;

     while(scanf("%d%d",&n,&m),n||m) {

         for(cnt = i = ; i < m; i++) {

             scanf("%d%d%d",&u,&v,&w);

             g[cnt++] = (arc) {u,v,w};

             g[cnt++] = (arc) {v,u,w};

         }

         bf();

         printf("%d\n",d[n]);

     }

     return ;

 }

spfa算法版：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <queue>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 #define pii pair<int,int>

 const int maxn = ;

 struct arc {

     int to,w;

 };

 vector<arc>g[maxn];

 queue<int>q;

 int n,m,d[maxn];

 bool done[maxn];

 void spfa() {

     int i,j;

     for(i = ; i <= n; i++){

         d[i] = INF;

         done[i] = false;

     }

     d[] = ;

     while(!q.empty()) q.pop();

     done[] = true;

     q.push();

     while(!q.empty()){

         int temp = q.front();

         q.pop();

         done[temp] = false;

         for(i = ; i < g[temp].size(); i++){

             j = g[temp][i].to;

             if(d[j] > d[temp]+g[temp][i].w){

                 d[j] = d[temp]+g[temp][i].w;

                 if(!done[j]){

                     q.push(j);

                     done[j] = true;

                 }

             }

         }

     }

 }

 int main() {

     int i,u,v,w;

     while(scanf("%d%d",&n,&m),n||m) {

         for(i = ; i <= n; i++)

             g[i].clear();

         for(i = ; i < m; i++) {

             scanf("%d%d%d",&u,&v,&w);

             g[u].push_back((arc){v,w});

             g[v].push_back((arc){u,w});

         }

         spfa();

         printf("%d\n",d[n]);

     }

     return ;

 }

巴特西