最短路径floyed算法思想用到三重循环枚举区间的起点终点和中间节点来不断松弛就可以找到最短路径但是三重循环太费时间。 dijkstra算法比佛洛依德快只需要两个循环 起点只有一个的情况枚举每个节点到起点的最短距离(用一维数组的下标来表示终点来存储) 不断地选取起点到某一个点的最短路径来松弛其他可以达到的点只需遍历n-1遍就可以实现详细的还需要通过题目去加深理解。
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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
这个题他用弗洛伊德就会超时
#include<bits/stdc++.h> using namespace std; int a[1009][1009],y[1500],pd[1009]; int main() { int m,n,e,b,c,u; while(~scanf("%d%d",&m,&n),m+n) { for(int i=0;i<=m;i++) { for(int j=0;j<=m;j++) { a[i][j]=0x3f3f3f3f; } } for(int i=0;i<n;i++) { cin>>e>>b>>c; a[e][b]=c; a[b][e]=c; } for(int i=1;i<=m;i++) y[i]=a[1][i]; memset(pd,0,sizeof(pd)); y[1]=0; pd[1]=1; for(int i=1;i<=m-1;i++) { int minn=0x3f3f3f3f; u=0; for(int j=1;j<=m;j++) { if(!pd[j]&&y[j]<minn) { minn=y[j]; u=j; } } if(u==0)break; pd[u]=1; for(int j=1;j<=m;j++) if(y[j]>y[u]+a[u][j]) y[j]=y[u]+a[u][j]; } printf("%d\n",y[m]); } }