题解：CF1693C Keshi in Search of AmShZ

· · 题解

我们倒着思考，考虑一种类似 DP 的方法：设 f_u 表示从点 u 走到目标点的最小代价，则有 f_u=\min\limits_{v \in nxt_u} (f_v+\sum\limits_{v' \in nxt_u}[f_{v'} > f_v] + 1)。

这个式子比较好理解：我们考虑我们最后一定会选一条边走出这个点，钦定当前选定的边是 u \to v，则首先把 f_{v'}>f_v 的边 u \to v' 封住一定是不劣的。然后由于现在要花时间向外走一步，故代价要加上 1。这样做就出现了一个问题：我们的图是存在环的，无法确定更新的先后顺序以在一次遍历中确定最终 f 的值，而每次暴力遍历所有点和其出边直到不能再更新 f 的值又会导致时间复杂度不可接受。

注意到 DP 值非负，考虑 Dijkstra trick 优化该 DP。我们从终点 n 开始采用类似 Dijkstra 的方式从小到大确定 f 的值，这样我们就能在 O(m \log m) 的时间复杂度内求解完所有的 DP 值。同时这样做我们 \sum 内的值也是容易计算的。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair <int , int>
#define pb push_back
#define fi first
#define se second
#define fastio ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
using namespace std;
const int MAXN = 2e5 + 10 , INF = 0x3f3f3f3f;
int n , m;
int f[MAXN] , cnt[MAXN];
bitset <MAXN> vis;
struct node
{
    int id;
    int val;
    bool operator < (const node &x) const {return val > x.val;}
};
vector <int> a[MAXN];
priority_queue <node> q;
void solve()
{
    q.push({n , 0});
    while(!q.empty())
    {
        auto now = q.top();
        q.pop();
        if(vis[now.id]) continue;
        vis[now.id] = 1;
        f[now.id] = now.val;
        for(int i : a[now.id])
        {
            if(vis[i]) continue;
            q.push({i , now.val + cnt[i]});
            cnt[i]--;
        }
    }
    return;
}
int main()
{
    fastio;
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        int u , v;
        cin >> u >> v;
        a[v].pb(u);
        cnt[u]++;
    }
    memset(f , INF , sizeof(f));
    solve();
    cout << f[1];
    return 0;
}