【CF思维训练】CF1693C Keshi in Search of AmShZ

小木虫 · 2023-02-23 20:04:08 · 题解

Preface

非常经典的类 Dijkstra 算法，同样类型的题目还有 [AHOI2014/JSOI2014]骑士游戏，[SDOI2010]大陆争霸。

Problem

给你一张 n 个点的有向连通图，你可以从点 1 开始沿着一条路径行走，沿着一条边行走花费 1 的时间，在某个点上时你可以花费 1 的时间断掉一条相邻的边，若沿着边行走的行动是完全随机的，即随机选择一条相邻边行走，问到达 n 点的最大时间的最小值。

Solution

如果你做过我说的那两道题，那么这道题在思维上应该对您来说十分简单。

具体来说，由于一个点到 n 点的最小代价由其后继决定，我们倒着考虑，设 f_u 为从 u 到 n 的最小代价，那么：

发现该转移方程是正权的，同时这是一个带环图，考虑 Dijkstra trick 优化这个 dp，即每一次我们取出一个 f 最小的点进行考虑，而那个求和符号后面的东西可以在一个一个转移的时候一个一个减，本质就是度数（因为我们先取 f 小的），没有做到的转移一定是无意义的。

code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,u,v,deg[N],vis[N],dis[N];
struct node{
    int u,dis;
    bool operator <(const node &a)const{
        return dis>a.dis;
    }
};
priority_queue <node> Q;
vector <int> edge[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>u>>v,edge[v].push_back(u),deg[u]++;
    fill(dis,dis+1+n,1e9);
    Q.push((node){n,0});dis[n]=0;
    while(!Q.empty()){
        int u=Q.top().u,w=Q.top().dis;
        Q.pop();if(vis[u])continue;vis[u]=1,dis[u]=w;
        for(int i=0;i<edge[u].size();i++){
            int v=edge[u][i];int w=deg[v]--;
            if(vis[v])continue;
            Q.push((node){v,dis[u]+w});
        }
    }cout<<dis[1];
    return 0;
}