最短路径算法问题

最短路径算法问题

题目:

给出一张包含n个节点、m条边的无向图（无重边，无自环），请你求出图上两点s,t间的最短路径长度。

其中1<=n<=500，1<=m<=10000，1<=任意边权<=500000；

Input

第一行两个数n,m，分别表示节点数和边数，以空格隔开； 之后m行，每行3个数u,v,w[i]，表示点u和v间有一条权值为w[i]的边； 最后一行，两个数s,t表示选择的两个点，以空格隔开。

Output

输出一个数，表示s,t间最短路径的长度。

Sample Input

4 3
1 2 6
1 3 4
2 4 2
3 4

Sample Output

12

思路：

该题主要通过Floyd-Warshall算法来解决；

其核心语句为：

for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
       if(e[i][j]>e[i][k]+e[k][j]
            e[i][j]=e[i][k]+e[k][j];
        

该代码的大致思想就是最开始只允许1号顶点进行中转，接下来是只允许1和2进行中转....允许经过1~n号所有顶点进行中转，求任意两点之间的最短距离就是从i号顶点到j号顶点只经过前k号顶点的最短路径。

代码：

#include
using namespace std;
long long a[502][502];
long long N=500000;
int main()
{
    int n, m,i,j,k;
    int x, y;
    long long e;
    scanf("%d %d", &n, &m);
        for (i = 1;i<=n;i++)
            for (j = 1;ja[i][k]+a[k][j]
                    a[i][j] = a[i][k]+a[k][j];
        scanf("%d %d",&x,&y);
        printf("%d",a[x][y]);
    return 0;
}