经典Dijkstra

#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30;
int n;
int dis[2501],cnt;
struct edge
{
	int x,y,w;
}Edge[20005];
void add(int x,int y,int z){
	Edge[cnt].x=x;
	Edge[cnt].y=y;
	Edge[cnt++].w=z;
}
void bellman(){
	int flag=1,i,j;
	for(j=0;j<n-1&&flag;j++){//做n-1次
		flag=0;
		for(i=0;i<cnt;i++) {
			int u=Edge[i].x,v=Edge[i].y,w=Edge[i].w;
			if(dis[u]+w<dis[v]) {//松弛
				flag=1;
				dis[v]=dis[u]+w;
			}
		}
	}
}
int main(){
	int c,s,e,x,y,z;
	cin>>n>>c>>s>>e;
	for(int i=1;i<=n;i++)dis[i]=INF;
	cnt=dis[s]=0;
	for(int i=1;i<=c;i++) {
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	bellman();
	printf("%d\n",dis[e]);
}