[SDOI2010] 大陆争霸题解-526互联

[题目传送门](https://www.luogu.com.cn/problem/P2446)

# 解法
由题可知，一个城市$u$保护城市$v$，所以建一条边$u \to v$表示城市$u$保护城市$v$，因为题目说保证有解，所以建的图一定是一个**有向无环图$DAG$** 。再在此基础上求出最短路径。

具体过程为设$dis_u$表示实际到达（攻破）$u$的最短时间，$arrive_u$表示到达$u$的时间（注意$arrive_u \neq dis_u$,而是$arrive_u \le dis_u$）。然后考虑怎么转移，我们发现$arrive_u$只会影响一个值就是$dis_u$，而$dis_u$能影响其他节点的$arrive$和$dis$值。

所以先考虑$arrive_u$的转移：

- $arrive_u=\min(dis_v,arrive_u)$，其中$v$为与$u$相邻的节点。显然$arrive_v$不能更新$dis_u$，因为$arrive_v$表示只是到达了$v$点，但可能还没有进入$v$点，所以不能这样更新。

然后再来考虑$dis_u$的转移：

- $dis_u=\max(arrive_u,dis_v)$，$v$表示保护$u$的节点编号。如果$arrive_u \le dis_v$表明到达$u$点可能还没有进入的最早时间比攻破$v$点的时间早，那么显然此时$dis_u$应该由$dis_v$决定。如果$arrive_u \ge dis_v$表明到达$u$点可能还没有进入的最早时间比攻破$v$点的时间晚，而因为此时保护$u$点的节点都被攻破了，所以由$arrive_u$来决定，即$dis_u=arrive_u$。

转移过想出来了，于是现在考虑用怎样的顺序能正确更新$dis_u$与$arrive_u$。我们发现上述过程与$dijkstra$算法的过程很相似，如果我们也每次取出$dis$值最小的点来进行更新就行。（ **为什么可以直接取出$dis$值最小的点进行更新？因为类似于$djikstra$的证明一定不存在另外的路径使得$dis$值再变小。** ）于是我们就可以用$dijkstra+topo$来实现啦。

# $Code$

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3050,M=70050;
long long dis[N],arrive[N],into[N];
int n,m;
int head[N],to[M],w[M],nxt[M],cnt,in[N];
bool vis[N];
vector<int> g[N];
void add(int u,int v,int f)
{
   to[++cnt]=v;
   nxt[cnt]=head[u];
   w[cnt]=f;
   head[u]=cnt;
}
struct node{
   long long val;int pos;
   bool operator >(const node &x)const{
       return val>x.val;
   }
};
void dij(int s)
{
   for(int i=1;i<=n;i++)dis[i]=arrive[i]=1e18;
   dis[s]=into[s]=arrive[s]=0;
   priority_queue<node,vector<node>,greater<node> >q;
   q.push(node{0,s});
   while(!q.empty())
   {
       node t=q.top();q.pop();
       if(vis[t.pos])continue;
//       cout<<t.pos<<endl;
       vis[t.pos]=1;
       for(int i=head[t.pos];i;i=nxt[i])
       {
           int v=to[i];
           if(arrive[v]>dis[t.pos]+w[i])
           {
               arrive[v]=dis[t.pos]+w[i];
               if(!in[v])
               {
                   dis[v]=max(into[v],arrive[v]);
                   q.push(node{dis[v],v});
//                   cout<<v<<endl;
               }
           }
       }
       for(auto v:g[t.pos])
       {
           in[v]--;
           into[v]=max(into[v],dis[t.pos]);
           if(!in[v])
           {
               dis[v]=max(arrive[v],into[v]);
               q.push(node{dis[v],v});
           }
       }
   }
   return;
}
int main()
{
   scanf("%d %d",&n,&m);
   for(int i=1,u,v,w;i<=m;i++)
   {
       scanf("%d %d %d",&u,&v,&w);
       add(u,v,w);
   }
   for(int i=1;i<=n;i++)
   {
       int x,v;
       scanf("%d",&x);
       while(x--)
       {
           scanf("%d",&v);
           g[v].push_back(i);
           in[i]++;
       }
   }
   dij(1);
   printf("%lld\n",dis[n]);
   return 0;
}
```

526互联

[SDOI2010] 大陆争霸 题解

[SDOI2010] 大陆争霸题解