题目描述

有一个 n 个点 m 条边的无向图，请求出从 s 到 t 的最短路长度。

输入格式

第一行四个正整数n,m,s,t。 接下来 mm 行，每行三个正整数u,v,w，表示一条连接u,v，长为 w 的边。

输出格式

输出一行一个整数，表示答案。

输入输出样例

输入 #1复制

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

输出 #1复制

7

说明/提示

【数据范围】
对于 100\%100% 的数据，1\le n \le 25001≤n≤2500，1\le m \le 62001≤m≤6200，1\le w \le 10001≤w≤1000。

【样例说明】
5 \to 6 \to 1 \to 45→6→1→4 为最短路，长度为 3+1+3 = 73+1+3=7。

 最基本的迪杰斯特拉模板即可解决

ac代码

#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
int n,m,s,t;
int a,b,l;
int v[2600][2600];
int dis[2600];
int book[2600];//初始化默认为0
int main()
{cin>>n>>m>>s>>t;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){if(i == j)v[i][j]=0;else v[i][j]=inf;}while(m--){cin>>a>>b>>l;v[a][b]=l;v[b][a]=l;}for(int i=1;i<=n;i++)dis[i]=v[s][i];book[s]=1;for(int i=1;i<=n-1;i++){int _min=inf,u;for(int j=1;j<=n;j++)//找到距离顶点最近的点{if(book[j] == 0 && dis[j] < _min){_min=dis[j];u=j;//并记录其坐标}}book[u]=1;for(int j=0;j<=n;j++)dis[j]=min(dis[j],dis[u]+v[u][j]);//比较s点到j的距离和s点到u再从u到j的距离，如果距离变短就替换}cout<<dis[t];return 0;
}