动漫网站设计,微信小程序会员管理系统怎么做,有网站制作app要多长时间,网站建设最难的部分给出一张包含 n 个节点、 m 条边的无向图#xff0c;请你求出图上两点 s,t 间的最短路径长度。
(请大家自行处理重边和自环)
Input
第一行两个数 n,m #xff0c;分别表示节点数和边数#xff0c;以空格隔开#xff0c;其中1≤n≤500,1≤m≤50000 #xff1b; 之后 m 行…给出一张包含 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
InputcopyOutputcopy 4 3
1 2 6
1 3 4
2 4 2
3 4 12
#includeiostream
#includealgorithm
#includecstring
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 i1;in;i) a[i][i] 0;int num3, num4;cin num3 num4;cout a[num3][num4] endl;
}
