题解 P2446 【[SDOI2010]大陆争霸】
bits
·
·
题解
简述题意：
~~顺便翻译一下本题中唯一的英文句子：~~
> 神谕：“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跑一边最短路即可。
```cpp
#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;
}
```