吉林市城市建设学校网站,免费推广网,导入表格做地图中热力网站,营销技巧视频讲座视频畅通工程续 题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1874 Problem Description 某省自从实行了很多年的畅通工程计划后#xff0c;终于修建了很多路。不过路多了也不好#xff0c;每次要从一个城镇到另一个城镇时#xff0c;都有许多种道路方案可以…畅通工程续 题目链接http://acm.hdu.edu.cn/showproblem.php?pid1874 Problem Description 某省自从实行了很多年的畅通工程计划后终于修建了很多路。不过路多了也不好每次要从一个城镇到另一个城镇时都有许多种道路方案可以选择而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。现在已知起点和终点请你计算出要从起点到终点最短需要行走多少距离。 Input 本题目包含多组数据请处理到文件结束。 每组数据第一行包含两个正整数N和M(0N200,0M1000)分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0N-1编号。 接下来是M行道路信息。每一行有三个整数A,B,X(0A,BN,A!B,0X10000),表示城镇A和城镇B之间有一条长度为X的双向道路。 再接下一行有两个整数S,T(0S,TN)分别代表起点和终点。 Output 对于每组数据请在一行里输出最短需要行走的距离。如果不存在从S到T的路线就输出-1. Sample Input 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2 Sample Output 2 -1 Author linle Source 2008浙大研究生复试热身赛2——全真模拟 解法一Dijkstra算法 #includeiostream #includecstdio #includecstring using namespace std; const int INF0x3f3f3f3f; const int N210; int n,m,s,t; int map[N][N],dis[N],vis[N]; void Dijkstra(int src){ int i; for(i0;in;i){ dis[i]map[src][i]; vis[i]0; } dis[src]0; vis[src]1; int j,k,tmp; for(i0;in;i){ tmpINF; for(j0;jn;j) if(!vis[j] tmpdis[j]){ kj; tmpdis[j]; } if(tmpINF) break; vis[k]1; for(j0;jn;j) if(!vis[j] dis[j]dis[k]map[k][j]) dis[j]dis[k]map[k][j]; } } int main(){ //freopen(input.txt,r,stdin); while(~scanf(%d%d,n,m)){ int u,v,w; for(int i0;in;i) for(int j0;jn;j) map[i][j]INF; for(int i0;im;i){ scanf(%d%d%d,u,v,w); if(map[u][v]w) map[u][v]map[v][u]w; } scanf(%d%d,s,t); Dijkstra(s); if(dis[t]INF) printf(-1\n); else printf(%d\n,dis[t]); } return 0; } 解法二SPFA算法 #includestdio.h #includeiostream #includequeue using namespace std; #define N 205 #define INF 99999999 int n,m,map[N][N]; int visited[N],dis[N]; int SPFA(int src,int des){ int i; for(i0;in;i){ dis[i]INF; visited[i]0; } queueint myqueue; while(!myqueue.empty()) myqueue.pop(); dis[src]0; visited[src]1; myqueue.push(src); int tmp; while(!myqueue.empty()){ tmpmyqueue.front(); myqueue.pop(); visited[tmp]0; for(i0;in;i) if(dis[i]dis[tmp]map[tmp][i]){ dis[i]dis[tmp]map[tmp][i]; if(!visited[i]){ visited[i]1; myqueue.push(i); } } } return dis[des]; } int main(){ int u,v,cost; while(scanf(%d%d,n,m)!EOF){ int i,j; for(i0;in;i) for(j0;jn;j) map[i][j]INF; for(i0;im;i){ scanf(%d%d%d,u,v,cost); if(costmap[u][v]) map[u][v]map[v][u]cost; } int s,t; scanf(%d%d,s,t); int ansSPFA(s,t); if(ansINF) printf(%d\n,ans); else printf(-1\n); } return 0; } 解法三Floyd算法 #includeiostream #includequeue #includecstdio #includecstring using namespace std; const int INF0x3f3f3f3f; const int N210; int n,m; int map[N][N]; void Floyd(){ int i,j,k; for(k0;kn;k) for(i0;in;i) for(j0;jn;j) if(map[i][j]map[i][k]map[k][j]) map[i][j]map[i][k]map[k][j]; } int main(){ //freopen(input.txt,r,stdin); while(~scanf(%d%d,n,m)){ int i,j; for(i0;in;i) for(j0;jn;j) map[i][j](ij?0:INF); //注意自身和自身距离为0。 int u,v,w; for(i0;im;i){ scanf(%d%d%d,u,v,w); if(map[u][v]w) map[u][v]map[v][u]w; } int s,t; scanf(%d%d,s,t); Floyd(); if(map[s][t]INF) printf(-1\n); else printf(%d\n,map[s][t]); } return 0; } Bellman_Ford #includeiostream #includequeue #includecstdio #includecstring using namespace std; const int INF0x3f3f3f3f; const int N210; int n,m,cnt; int dis[N]; struct node{ int u,v; int w; }edge[1010*2]; void addedge(int u,int v,int w){ edge[cnt].uu; edge[cnt].vv; edge[cnt].ww; cnt; edge[cnt].uv; edge[cnt].vu; edge[cnt].ww; cnt; } int Bellman_Ford(int src,int des){ int i,k; for(i0;in;i) dis[i]INF; dis[src]0; for(k0;kn-1;k) for(i0;icnt;i) if(dis[edge[i].u]!INF dis[edge[i].v]dis[edge[i].u]edge[i].w) dis[edge[i].v]dis[edge[i].u]edge[i].w; return dis[des]INF?-1:dis[des]; } int main(){ //freopen(input.txt,r,stdin); while(~scanf(%d%d,n,m)){ cnt0; int u,v,w; for(int i0;im;i){ scanf(%d%d%d,u,v,w); addedge(u,v,w); } int s,t; scanf(%d%d,s,t); printf(%d\n,Bellman_Ford(s,t)); } return 0; } 在网上搜索得到的觉得写得挺好自己也总结不了那么全就先转载过来 原文链接http://www.cnblogs.com/jackge/archive/2013/01/01/2841536.html
