#include<bits/stdc++.h>
using namespace std;
#define pii pair < int , int >
#define mp make_pair
priority_queue < pii , vector < pii > , greater < pii > > q;
int n,c;
int h[5001];
int nt[100001*2];
int to[100001*2];
int W[100001*2];
int cnt;
void add(int x,int y,int z){
nt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
W[cnt]=z;
}
int dis[5001],dist[5001];
int vis[5001];
void dijkstra()
{
for(int i=1; i<=n; i++)
dist[i]=dis[i]=99999999;
dist[1]=0;
q.push(mp(0,1));
while(!q.empty()){
int x=q.top().second;
q.pop();
for(int i=h[x]; i; i=nt[i])
{
int y=to[i],w=W[i];
//cout<<x<<" "<<y<<" "<<dist[x]+w<<endl;
if(dist[x]+w<dist[y]){
dis[y]=dist[y];
dist[y]=dist[x]+w;
q.push(mp(dist[y],y));
}
else{
if(dist[x]+w<dis[y]&&dist[y]!=dist[x]+w)
{
dis[y]=dist[x]+w;
q.push(mp(dis[y],y));
}
}
if(dis[y]>dis[x]+w)
dis[y]=dis[x]+w;
}
}
cout<<dis[n]<<endl;
}
int main(){
//freopen("text.in","r",stdin);
cin>>n>>c;
for(int i=1; i<=c; i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dijkstra();
}
标签:pii,cnt,int,5001,Roadblocks,add,P2865,USACO06NOV,100001
From: https://www.cnblogs.com/dadidididi/p/16803835.html