题解 P2865 【[USACO06NOV]路障Roadblocks】

Fheiwn · 2017-10-17 19:01:59 · 题解

一道果的次短路问题；

我是用的dijkstra;

最短路的思想都会。

次短路 dis2<s,t> 有两种情况

(1) : 从s->u的最短路+dis<u,t>;

(2) : 从s->u的次短路+dis<u,t>;

所以 只要在跑最短路时 记录次短路(dis2) 并更新。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<bitset>
#include<sstream>
#include<cstdlib>
#define QAQ int
#define TAT long long
#define ORZ double
#define OwO bool
#define SHO short
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))
using namespace std;
const QAQ N=5005,M=200005;
typedef pair<QAQ,QAQ> PA;
QAQ n,m;
struct data{
    QAQ to,last,val;
}a[M];
QAQ head[N],js;
QAQ dis1[N],dis2[N];
priority_queue<PA,vector<PA>,greater<PA> > q;
void dijkstra(QAQ s){
    MES(dis1,100);MES(dis2,100);
    dis1[s]=0;
    q.push(make_pair(dis1[s],s));
    while(q.size()){
        PA p=q.top();q.pop();
        QAQ x=p.second,dis=p.first;
        if(dis>dis2[x]) continue;
        for(QAQ i=head[x];i;i=a[i].last){
            QAQ d2=dis+a[i].val;
            if(dis1[a[i].to]>d2){
                swap(dis1[a[i].to],d2);
                q.push(make_pair(dis1[a[i].to],a[i].to));
            }
            if(dis2[a[i].to]>d2&&dis1[a[i].to]<d2){
                dis2[a[i].to]=d2;
                q.push(make_pair(dis2[a[i].to],a[i].to));
            }
        }
    }
}
void add(QAQ x,QAQ y,QAQ z){
    a[++js].to=y;a[js].val=z;
    a[js].last=head[x];head[x]=js;
}
QAQ main(){
    scanf("%d%d",&n,&m);
    F(i,1,m) {
        QAQ u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    dijkstra(1);
    printf("%d\n",dis2[n]);
    return 0;
}