最短路有关问题 以hdu1874为例

最短路问题 以hdu1874为例

题目链接：点击打开链接

hdu 1874比较基础，拿来练各种刚学会的算法比较好，可以避免好多陷阱，典型的最短路模板题
 
第一种解法：Floyd算法 算法实现：
使用一个邻接矩阵存储边权值，两两之间能访问的必为一个有限的数，不能访问则为无穷大（用2^29代替）。注意自身和自身距离为0。
对于一对顶点 u 和 v，看看是否存在一个断点 w 使得从 u 经过 w 到 v 比已知的路径更短（包含原始输入中从 u 直接到 v 的路程）。
对所有顶点进行如上松弛操作，得到的结果是两点之间的最短路程，也可判断两点是否连通。
算法缺点：

普通的Floyd算法时间复杂度为O(n^3)，对于数据较多的情况容易TLE。但解决本题 HDU 1874 完全足够。

#include<stdio.h>//SPFA 模拟队列实现最短路径#include<string.h>#define INF 100000int map[210][210],flag[210],Q[210],d[210];int m,n,start,tar;void SPFA(){   int i,x;   int front=0,rear=0;   memset(Q,0,sizeof(Q));   memset(flag,0,sizeof(flag));   for(i=0;i<n;i++)       d[i]=INF;   d[start]=0;   Q[rear]=start;   rear++;   flag[start]=1;   while(front<rear)   {       x=Q[front];//出队列       front=(front+1)%210;       flag[x]=0;       for(i=0;i<n;i++)       {           if(d[i]>d[x]+map[x][i])           {               d[i]=d[x]+map[x][i];               if(!flag[i])               {                   Q[rear]=i;//入队列                   rear=(rear+1)%210;                   flag[i]=1;               }           }       }   }   if(d[tar]<INF)       printf("%d\n",d[tar]);   else printf("-1\n");}int main(){   int i,j,a,b,c;   while(scanf("%d%d",&n,&m)!=EOF)   {       for(i=0;i<n;i++)           for(j=0;j<n;j++)               map[i][j]=INF;       for(i=0;i<m;i++)       {           scanf("%d%d%d",&a,&b,&c);           if(map[a][b]>c)           map[a][b]=map[b][a]=c;       }       scanf("%d%d",&start,&tar);       SPFA();   }   return 0;}

其实最短路总结就一句话，不断的进行松弛操作，无论是什么解法，都要进行松弛操作，然后找到最短路径

查看更多 下一篇