[SDOI2010] 大陆争霸 题解

[题目传送门](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;
}
```