点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=3000;
const int M=7000*2;
int n,m,s,t;
struct Edge{int to;int w;int ne;
}edge[M];
int h[N];
int idx;
int dist[N];
bool st[N];int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({dist[s],s});while(!heap.empty()){auto t=heap.top();heap.pop();auto ver=t.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=edge[i].ne){int j=edge[i].to;if(dist[j]>dist[ver]+edge[i].w){dist[j]=dist[ver]+edge[i].w;heap.push({dist[j],j});}}}return dist[t];
}void add(int u,int v,int w)
{edge[idx].w=w;edge[idx].to=v;edge[idx].ne=h[u];h[u]=idx++;
}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s>>t;memset(h,-1,sizeof h);while(m--){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);}cout<<dijkstra()<<endl;
}