阜阳网站推广爱站站长工具

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

(请大家自行处理重边和自环)

Input

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

Output

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

Data Description

对于 27% 的数 n≤10 ， m≤50 ；
对于 70% 的数据， n≤100 ，m≤5000 ；
对于 100% 的数据，n≤500 ，m≤50000 ,1≤w[i]≤500000 ；

Sample 1

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

12

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int a[N][N];int n, m;void floyd()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}int main()
{memset(a, INF, sizeof a);cin >> n >> m;for (int i = 1; i <= m; i++){int num1, num2, num3;cin >> num1 >> num2 >> num3;a[num1][num2] = a[num2][num1] = min(a[num1][num2],num3);}floyd();for(int i=1;i<=n;i++) a[i][i] = 0;int num3, num4;cin >> num3 >> num4;cout << a[num3][num4] << endl;
}