P2865 [USACO06NOV]Roadblocks G

标签：pii cnt int 5001 Roadblocks add P2865 USACO06NOV 100001

#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