自动搬运

查看原文

来自洛谷，原作者为

	bits 。。。

搬运于2025-08-24 21:37:47，当前版本为作者最后更新于2019-03-03 12:42:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简述题意：

$m$条单向边连接$n$个城市，通过每边要$w_i$单位时间。从$1$开始，依次摧毁城市，仅仅摧毁不用时间，直到摧毁$n$结束。部分城市被别的城市保护，只有保护它的城市被摧毁后，才能摧毁这个城市。求结束的最短时间。

顺便翻译一下本题中唯一的英文句子：

神谕：“Trust me, earn eternal life.”

“相信我，获得永恒的生命。”

以上结果来自百度翻译。

解法

由题可知，有的城市被保护。设$u$被$v$保护，我们从$v$建一条有向边到$u$，并记录$u$的入度$ind[u]$。广度遍历图，在摧毁$v$时，删去$v$到$u$的边，并更新入度。当$ind[u]=0$时，方可进入城市$u$。

设$arrive[i]$表示到达$i$的时间（可能要在门口等待）。设$into[i]$为进入$i$的时间（即什么时候所有保护$i$的城市被摧毁了）。设$dis[i]$表示摧毁$i$的时间，可得$dis[i]=max(arrive[i],into[i])$。设{ $j_n$ }为$i$的所有前驱，则$into[i]=max$ { $into[j_n]$ } 。

用Dijkstra跑一边最短路即可。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

char ss[1<<17],*A=ss,*B=ss;//快读
inline char gc(){
    return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?EOF:*A++;
}
template<typename qRead>
inline void qr(qRead &s){
    char c=gc(); 
    s=0;
    for(;c<'0'||c>'9';c=gc());
    for(;c>='0'&&c<='9';c=gc())
        s=(s<<1)+(s<<3)+(c-'0');
}

const int N=3001,M=200001;
//题目中没有说有多少对保护关系，所以开大点
struct Edge{//存储路径
    int node,next,val;
}edge[M];
int heade[N],n,m,tote;
struct Graph{//存储保护关系
    int node,next;
}graph[M];
int headg[N],totg;

struct qnode{
    int key,len;
    friend bool operator < (qnode x,qnode y){
        return x.len<y.len;//负的边权+大根堆，实际就是最短路
    }
};
int dis[N],into[N],ind[N],arrive[N];
bool vis[N];
priority_queue<qnode> q;

void dijkstra(int s){//模板
    for(int i=1;i<=n;i++)
        dis[i]=arrive[i]=1e9;
    dis[s]=into[s]=arrive[s]=0;
    ind[s]=0;
    q.push((qnode){s,0});
    int u,v;
    while(!q.empty()){
        u=q.top().key;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int k=heade[u];k;k=edge[k].next){
            v=edge[k].node;
            if(dis[u]+edge[k].val<arrive[v]){
                arrive[v]=dis[u]+edge[k].val;
                if(!ind[v]){//记得更新摧毁的时间~~~
                    dis[v]=max(into[v],arrive[v]);
                    q.push((qnode){v,-dis[v]});
                }
            }
        }
        for(int k=headg[u];k;k=graph[k].next){
            v=graph[k].node;
            into[v]=max(into[v],dis[u]);//摧毁当前节点，逐层删去保护关系
            ind[v]--;
            if(!ind[v]){//怎么有点像拓扑排序
                dis[v]=max(into[v],arrive[v]);
                q.push((qnode){v,-dis[v]});
            }
        }
    }
}

int main(){
    qr(n);
    qr(m);
    int x,y,l;
    while(m--){
        qr(x);
        qr(y);
        qr(l);
        edge[++tote].node=y;
        edge[tote].next=heade[x];
        edge[tote].val=l;
        heade[x]=tote;
    }
    for(int i=1;i<=n;i++){
        qr(x);
        while(x--){
            qr(y);
            ++ind[i];//建立保护关系
            graph[++totg].node=i;
            graph[totg].next=headg[y];
            headg[y]=totg;
        }
    }
    dijkstra(1);
    printf("%d\n",dis[n]);
    return 0;
}