https://vjudge.net/problem/17632/origin
上代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<functional> #include<queue> using namespace std; const int maxn=1e3+5; const int inf=0x3f3f3f3f; typedef pair<int,int> P; vector<P> G[maxn]; int d[maxn]; void init(int n){ for(int i=0;i<n;i++)d[i]=inf; for(int i=0;i<n;i++)G[i].clear(); } void dijkstra(int s){ priority_queue<P,vector<P>,greater<P> >Q; d[s]=0; Q.push(make_pair(d[s],s)); while(!Q.empty()){ int now=Q.top().second; Q.pop(); for(int i=0;i<G[now].size();i++){ int v=G[now][i].first; if(d[v]>d[now]+G[now][i].second){ d[v]=d[now]+G[now][i].second; Q.push(make_pair(d[v],v)); } } } } int main(){ int n,m; while(cin>>n>>m){ init(n); for(int i=1;i<=m;i++){ int x,y,v; cin>>x>>y>>v; G[x].push_back(make_pair(y,v)); G[y].push_back(make_pair(x,v)); } int s,t; cin>>s>>t; dijkstra(s); if(d[t]==inf)cout<<"-1"<<endl; else cout<<d[t]<<endl; } return 0; }