折扣网站怎么做,报考二级建造师证需要什么条件,wordpress设置新窗口打开链接,科技类网站链接#xff1a; http://acm.hdu.edu.cn/showproblem.php?pid2544 题目#xff1a; Problem Description 在每年的校赛里#xff0c;所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候#xff0c;却是非常累的…链接 http://acm.hdu.edu.cn/showproblem.php?pid2544 题目 Problem Description 在每年的校赛里所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候却是非常累的所以现在他们想要寻找最短的从商店到赛场的路线你可以帮助他们吗 Input 输入包括多组数据。每组数据第一行是两个整数N、MN100M10000N表示成都的大街上有几个路口标号为1的路口是商店所在地标号为N的路口是赛场所在地M则表示在成都有几条路。NM0表示输入结束。接下来M行每行包括3个整数ABC1A,BN,1C1000,表示在路口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 Source UESTC 6th Programming Contest Online 基础最短路不解释其实是专门用来验证各种最短路模板的。 在网上搜索的某神的博客这些模板题其实没什么来讲的自己再敲一遍和这也差不太远图论的话多看书 附原文链接 http://blog.csdn.net/shuangde800 1. Dijkstra 普通版 [cpp] view plaincopy #includecstdio #includecstring const int N105, INF9999999; int d[N], w[N][N],vis[N],n,m; void Dijkstra(int src){ for(int i1; in; i) d[i] INF; d[src] 0; memset(vis, 0, sizeof(vis)); for(int i1; in; i){ int u-1; for(int j1; jn; j)if(!vis[j]){ if(u-1 || d[j]d[u]) uj; } vis[u] 1; for(int j1; jn; j)if(!vis[j]){ int tmp d[u] w[u][j]; if(tmpd[j]) d[j] tmp; } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ for(int i1; in; i){ w[i][i] INF; for(int ji1; jn; j) w[i][j] w[j][i] INF; } for(int i0; im; i){ scanf(%d%d%d,a,b,c); w[a][b] w[b][a] c; } Dijkstra(1); printf(%d\n, d[n]); } return 0; } 2. Dijkstra邻接表(用数组实现)优先队列优化 [cpp] view plaincopy #includecstdio #includecstring #includeutility #includequeue using namespace std; const int N20005; const int INF9999999; typedef pairint,intpii; priority_queuepii, vectorpii, greaterpii q; int d[N], first[N], u[N], v[N], w[N], next[N],n,m; bool vis[N]; // 无向图的输入注意每输入的一条边要看作是两条边 void read_graph(){ memset(first, -1, sizeof(first)); //初始化表头 for(int e1; em; e){ scanf(%d%d%d,u[e], v[e], w[e]); u[em] v[e]; v[em] u[e]; w[em] w[e]; // 增加一条它的反向边 next[e] first[u[e]]; // 插入链表 first[u[e]] e; next[em] first[u[em]]; // 反向边插入链表 first[u[em]] em; } } void Dijkstra(int src){ memset(vis, 0, sizeof(vis)); for(int i1; in; i) d[i] INF; d[src] 0; q.push(make_pair(d[src], src)); while(!q.empty()){ pii u q.top(); q.pop(); int x u.second; if(vis[x]) continue; vis[x] true; for(int e first[x]; e!-1; enext[e]) if(d[v[e]] d[x]w[e]){ d[v[e]] d[x] w[e]; q.push(make_pair(d[v[e]], v[e])); } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ read_graph(); Dijkstra(1); printf(%d\n, d[n]); } return 0; } 3. Dijkstra邻接表(用vecor实现)优先队列优化 [cpp] view plaincopy #includecstdio #includecstring #includeutility #includequeue #includevector using namespace std; const int N105; const int INF9999999; typedef pairint,intpii; vectorpiiG[N]; priority_queuepii, vectorpii, greaterpii q; int d[N], first[N], u[N], v[N], w[N], next[N],n,m; bool vis[N]; // 无向图的输入注意没输入的一条边要看作是两条边 void read_graph(){ for(int i1; in; i) G[i].clear(); int a,b,c; for(int i1; im; i){ scanf(%d%d%d,a,b,c); G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } } void Dijkstra(int src){ memset(vis, 0, sizeof(vis)); for(int i1; in; i) d[i] INF; d[src] 0; q.push(make_pair(d[src], src)); while(!q.empty()){ pii t q.top(); q.pop(); int u t.second; if(vis[u]) continue; vis[u] true; for(int v0; vG[u].size(); v)if(d[G[u][v].first] d[u]G[u][v].second){ d[G[u][v].first] d[u]G[u][v].second; q.push(make_pair(d[G[u][v].first], G[u][v].first)); } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ read_graph(); Dijkstra(1); printf(%d\n, d[n]); } return 0; } 二Bellman-Ford算法 [cpp] view plaincopy #includecstdio #includecstring #includeutility #includequeue using namespace std; const int N20005; const int INF9999999; int n, m, u[N],v[N],w[N], d[N]; // 无向图的输入注意每输入的一条边要看作是两条边 inline void read_graph(){ for(int e1; em; e){ scanf(%d%d%d,u[e],v[e],w[e]); } } inline void Bellman_Ford(int src){ for(int i1; in; i) d[i] INF; d[src] 0; for(int k0; kn-1; k){ for(int i1; im; i){ int xu[i], yv[i]; if(d[x] INF){ if(d[y]d[x]w[i]) d[y] d[x]w[i]; } if(d[y] INF){ if(d[x]d[y]w[i]) d[x] d[y]w[i]; } } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ read_graph(); Bellman_Ford(1); printf(%d\n, d[n]); } return 0; } 三SPFA 邻接表实现 [cpp] view plaincopy #includecstdio #includecstring #includeutility #includequeue using namespace std; const int N20005; const int INF21474836461; int n, m, first[N],next[N],u[N],v[N],w[N], d[N]; bool vis[N]; queueintq; inline void read_graph(){ memset(first, -1, sizeof(first)); for(int e1; em; e){ scanf(%d%d%d,u[e],v[e],w[e]); u[em]v[e], v[em]u[e], w[em]w[e]; next[e] first[u[e]]; first[u[e]] e; next[em] first[u[em]]; first[u[em]] em; } } void SPFA(int src){ memset(vis, 0, sizeof(vis)); for(int i1; in; i) d[i] INF; d[src] 0; vis[src] true; q.push(src); while(!q.empty()){ int x q.front(); q.pop(); vis[x] false; for(int efirst[x]; e!-1; enext[e]){ if(d[x]w[e] d[v[e]]){ d[v[e]] d[x]w[e]; if(!vis[v[e]]){ vis[v[e]] true; q.push(v[e]); } } } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ read_graph(); SPFA(1); printf(%d\n, d[n]); } return 0; } 四 Floyd算法 [cpp] view plaincopy #includecstdio #includecstring #includeutility #includequeue using namespace std; const int N105; const int INF2147483646; int n, m, d[N][N]; inline void read_graph(){ for(int i1; in; i){ d[i][i] INF; for(int ji1; jn; j) d[i][j]d[j][i]INF; } int a,b,c; for(int e1; em; e){ scanf(%d%d%d,a,b,c); d[a][b]d[b][a]c; } } inline void Floyd(int src){ for(int k1; kn; k){ for(int i1; in; i){ for(int j1; jn; j) if(d[i][k]INF d[k][j]INF){ //防止溢出 d[i][j] min(d[i][j], d[i][k]d[k][j]); } } } } int main(){ int a,b,c; while(~scanf(%d%d,n,m)nm){ read_graph(); Floyd(1); printf(%d\n, d[1][n]); } return 0; }