P2865 [USACO06NOV]路障Roadblocks

P2865 [USACO06NOV]路障Roadblocks

最短路（次短路）

直接在dijkstra中维护2个数组：d1（最短路）,d2（次短路），然后跑一遍就行了。

attention：数据有不同权值的重边（40ptsQAQ）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cctype>

using namespace std;

template <typename T> inline void read(T &x){

    char c=getchar(); x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

}

struct data{

    int d,u;

    bool operator < (const data &tmp) const {return d>tmp.d;}

}; priority_queue <data> h;

int n,m,cnt,d1[],d2[],hd[],nxt[],ed[],poi[],val[];

inline void add(int x,int y,int v){

    nxt[ed[x]]=++cnt; hd[x]=hd[x] ? hd[x]:cnt;

    ed[x]=cnt; poi[cnt]=y; val[cnt]=v;

}

int main(){

    read(n); read(m); int q1,q2,q3;

    for(int i=;i<=m;++i) read(q1),read(q2),read(q3),add(q1,q2,q3),add(q2,q1,q3);

    memset(d1,,sizeof(d1));

    memset(d2,,sizeof(d2));

    h.push((data){d1[]=,});

    while(!h.empty()){

        data x=h.top(); h.pop();

        if(x.d!=d1[x.u]&&x.d!=d2[x.u]) continue;

        for(int i=hd[x.u];i;i=nxt[i]){

            if(x.d+val[i]<d1[poi[i]]){ //最短路更新

                d2[poi[i]]=d1[poi[i]];

                d1[poi[i]]=x.d+val[i];

                h.push((data){d1[poi[i]],poi[i]});

            }else if(x.d+val[i]<d2[poi[i]]){ //次短路更新

                d2[poi[i]]=x.d+val[i];

                h.push((data){d2[poi[i]],poi[i]});

            }

        }

    }printf("%d",d2[n]);

    return ;

}