Codeforces Round 800 (Div. 2)

Keshi in Search of AmShZ

算法本质

思维！

题目大意

给定一个有向图，Alice在点1，希望走到点n，玩家每回合可以执行某个操作：

• 删除某条边
• 指挥Alice前进，Alice会随机选择一条可行的边前进

输出最小化的至多操作次数。

思路推演

稍加思索可以发现，如果没有环，这就是一个十分简单的反向topo（含有一丢丢思维）：

• 若对于u点来说，其有4个出点，其到n点的路是1 4 7 8
  如果不进行删除，则需要8步
  进行一次删除，则是1+1 4+1 7+1，还是需要8步
  进行2次删除需要6步
  进行3次删除需要4步，显然我们选择4步的

现在来解决环的问题。
看似环特别难，因为大家相互牵制、依赖。但是其数据范围1e5，其实反而是告诉我们，这个算法简单而高效。

Dijkstra !

这也是k短路的核心思想

回想有向图，面临这种多样的情况时，dj最短路给出了思路：暴力维护最优即可。

其解决环的核心在于，找到环中最近的点，这个最近不仅是距离最近，而是删除若干边后的最近。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n>>m;
    vector<vector<int>> g(n+5);
    vector<int> chu(n+5), vis(n+5), dis(n+5, 1e9);
    while (m--)
    {
        int u, v;
        cin>>u>>v;
        g[v].push_back(u);
        chu[u]++;
    }
    priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> q;    // !
    q.push({0, n});
    dis[n] = 0;
    while (q.size())
    {
        auto [last, u] = q.top();
        q.pop();
        if (vis[u])        continue;
        vis[u] = 1;
        dis[u] = last;
        for (int v:g[u])
        {
            q.push({last + chu[v], v});
            chu[v]--;
        }
    }
    int ans = dis[1];
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。