【头歌实训：单源最短路径】

头歌实训：单源最短路径
给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。

文章目录

• 输入格式:
• 输出格式:
• 输出样例:
• 注意:
• 源代码：

输入格式:

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

之后的 m 行，每行三个正整数 s_i 、t_i 、w_i(1 ≤w_i≤ 1 0 9 10^{9} 109)，表示一条从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<iostream>
#define  N 3000
int e[N][N],dis[N],book[N];
int main(){
	
	int i,j,n,m,t1,t2,t3,u,v,min,s,t;
	int inf=99999999;

	cin>>n>>m>>s>>t;

//初始化
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
				else e[i][j]=inf;
		}
	}
//读入边
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>t3;
		e[t1][t2]=t3;
		e[t2][t1]=t3;	//去掉该向变成有向图
	}

//初始化dis数组，这里1号顶点到其余各个顶点的初始路程
	for(i=1;i<=n;i++){
		dis[i]=e[s][i];
	}
//book数组初始化
	for(i=1;i<=n;i++)
		book[i]=0;

	book[i]=1;
//Dijkstra算法核心
	for(i=1;i<=n-1;i++){
		min=inf;	//找到离1号顶点最近的顶点
		for(j=1;j<=n;j++){

			if(book[j]==0 && dis[j]<min){
				min=dis[j];
				u=j;
			}

		}
		book[u]=1;

		for(v=1;v<=n;v++){
			if(e[u][v]<inf){

				if(dis[v]>dis[u]+e[u][v])
					dis[v]=dis[u]+e[u][v];
			}
		}
	}
	//输出结果
		cout<<dis[t];
		
	return 0;
}