单源最短路
//dijkstra算法+配对堆优化计算单源最短路
#include<stdio.h>
#include<stdbool.h>
struct node{
struct node *fa,*l,*r;
int data,p;
}buf[1000000];int ind=-1;
struct node* root;
struct node* _merge(struct node* u,struct node* v){
(v->r=u->l)?v->r->fa=v:0;
return u->l=v,v->fa=u;
}
#define merge(u,v) (u->data<v->data?_merge(u,v):_merge(v,u))
struct node* combine(struct node* rt){
if(rt->r==0)return rt;
static struct node* arr[100000];int j=-1;
for(;rt!=0;rt=rt->r)arr[++j]=rt,rt->fa->r=0;
for(int i=0;i<j;i+=2)arr[i]=merge(arr[i],arr[i|1]);
for(j&1!=0?j^=1:0;j>0;j-=2)arr[j-2]=merge(arr[j-2],arr[j]);
return arr[0];
}
struct node* push(int x,int p){
struct node* t=&buf[++ind];t->data=x;t->p=p;
return root=root==0?t:merge(root,t),t;
}
void pop(){
root=root->l!=0?combine(root->l):0;
}
void dec(struct node* p,int k){
p->data=k;
if(p==root)return;
if(p->r!=0)p->r->fa=p->fa;
if(p->fa->l==p)p->fa->l=p->r;
else p->fa->r=p->r;
p->r=0;
root=merge(root,p);
}
typedef int arr[10000];
typedef int ard[100000];
arr head,dis;bool vis[10000];
ard to,next,w;
struct node* hp[10000];
void ae(int u,int v,int ww){
static int ind=1;
to[++ind]=v;w[ind]=ww;next[ind]=head[u];head[u]=ind;
to[++ind]=u;w[ind]=ww;next[ind]=head[v];head[v]=ind;
}
int n,m,s,t;
void dijkstra(int s){
for(int i=1;i<=n;i++)dis[i]=1e9;dis[s]=0;
for(int i=1;i<=n;i++)hp[i]=push(dis[i],i);
while(root){
int v=root->p;pop();
if(vis[v])continue;vis[v]=1;
for(int i=head[v];i;i=next[i])
if(dis[to[i]]>dis[v]+w[i]){
dis[to[i]]=dis[v]+w[i];
dec(hp[to[i]],dis[to[i]]);
}
}
}
int main(){
int u,v,ww;
scanf("%d%d%d%d",&n,&m,&s,&t);//共n个点,m条边,计算从编号s到编号t点间最短路
for(int i=0;i<m;++i){
scanf("%d%d%d",&u,&v,&ww);//编号u,编号v点间有一条长度ww的路
ae(u,v,ww);
}
dijkstra(s);
printf("%d",dis[t]);
return 0;
}