北京电力交易中心电力交易平台_美工培训机构靠谱吗_百度怎么推广自己的网站_seo 页面链接优化

任务要求：

给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。

输入格式:
第一行四个由空格隔开的整数 n、m、s、t。

之后的 m 行，每行三个正整数 S i​、Ti、W i(1≤W i≤)，表示一条从S i到 T i长度为 W i的边。

输出格式:
一个整数，表示从s 到t 的最短路径长度。数据保证至少存在一条道路。

输入样例:
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例:
7
注意:
两个顶点之间可能存在多条直接相连的道路。

测试代码 

#include <bits/stdc++.h>
using namespace std;

补充代码： 

#include <bits/stdc++.h>
using namespace std;
int e[2502][2502]={10000};
int f[2502],n,m,dist[2502];int main(){int j,i,x,y,z,s,t;scanf("%d %d %d %d",&n,&m,&s,&t);for(i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&z);if(e[x][y]==0||e[x][y]>z){e[x][y]=z;e[y][x]=z;}//printf("%d\n",e[x][y]);}int min,mini;for(i=1;i<=n;i++){dist[i]=e[s][i];f[i]=0;//printf("%d\n",dist[i]);}f[s]=1;dist[s]=0;mini=s;for(i=1;i<=n;i++){min=1000000;;for(j=1;j<=n;j++){if(f[j]==0&&dist[j]<min&&dist[j]!=0){mini=j;min=dist[j];}}//printf("%d\n",min);if(mini==t){printf("%d\n",min);break;}f[mini]=1;for(j=1;j<=n;j++){if(f[j]==0&&e[mini][j]!=0){if(dist[j]==0||dist[j]>(dist[mini]+e[mini][j])){dist[j]=dist[mini]+e[mini][j];}}}}
}