Luogu

分析

关于题面

设 $dis1[i]$ 表示到达 $i$ 的最短时间,$dis2[i]$ 表示破除 $i$ 的防御的最短时间。那么答案就是 $\max\{dis1[n],dis2[n]\}$ 。

于是先用道路更新 $dis1$ ,然后再用结界的关系更新 $dis2$ 即可。

然后如果破除防御了就可以丢到堆里去。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10,M=200000+10;

int n,m,li[N];

struct Graph {
    struct edge { int v,w,nxt; } e[M];
    int head[N];
    inline void addEdge(int u,int v,int w=0) {
        static int cnt=0;
        e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
    }
} A,B;

int dis1[N],dis2[N];
struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
inline void dijkstra() {
    priority_queue<node> Q; memset(dis1,0x3f,sizeof(dis1));
    dis1[1]=0,Q.push((node){1,0});
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (max(dis1[u],dis2[u])!=d) continue;
        for (re int i=A.head[u];i;i=A.e[i].nxt) {
            int v=A.e[i].v,w=A.e[i].w;
            if (d+w<dis1[v]) {
                dis1[v]=d+w;
                if (!li[v]) Q.push((node){v,max(dis1[v],dis2[v])});
            }
        }
        for (re int i=B.head[u];i;i=B.e[i].nxt) {
            int v=B.e[i].v;
            --li[v],dis2[v]=max(dis2[v],d);
            if (!li[v]) Q.push((node){v,max(dis1[v],dis2[v])});
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        A.addEdge(u,v,w);
    }
    for (re int i=1;i<=n;++i) {
        li[i]=read();
        for (re int j=1;j<=li[i];++j) B.addEdge(read(),i);
    }
    dijkstra(); printf("%d\n",max(dis1[n],dis2[n]));
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 22 PM