题目传送门

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int dist[N];
int vis[N],mp[N][N];
int dijstra(int n){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=1;i<=n;i++){
		int index=-1;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&(dist[j]<dist[index]||index==-1)){
				index=j;
			}
		}
		vis[index]=1;
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],dist[index]+mp[index][j]);
		}
	}
	if(dist[n]==0x3f3f3f3f) return (1<<31)-1;
	else return dist[n];
}
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	while(m--){
		int a,b,c; cin>>a>>b>>c;
		mp[a][b]=c;
	}
	cout<<dijstra(s)<<endl;
	return 0;
}