【题意】
给出一张 \(n\) 个点 \(m\) 条边的有向图，有一个人要从 \(1\) 走到 \(n\)。每天，你可以给他其中一种提示：
- 封锁某一条边，即告诉他这条边之后都不能走。
- 告诉他移动，他会等概率地选择一条未封锁的出边走过去。
求保证他能成功从 \(1\) 走到 \(n\) 的最小天数 \(d\)（无论第二种随机走哪条出边都能在 \(d\) 天内到达 \(n\)）。
\(2\leq n\leq 2\times 10^5, 1\leq m\leq 2\times 10^5\)
【分析】
首先考虑如果是个 DAG 显然有 dp：知道了 \(i\) 后继节点的所有 dp 值之后从大到小排序，设分别为 \(dp_0,dp_1,...,dp_k\)。那么
\[dp_i = \min \limits_{j = 0}^k \{dp_j + j + 1\} \]其实 \(j\) 也就是选择这条边需要封堵的边数。
然后发现有环做不了。这时候应该考虑特性，找思路，或者干脆直接枚举思路：有环，正权，dijkstra 是不是可以解决？
考虑 dijkstra 的正确性（思路不能迷糊！）：基于贪心，任意时刻最小的那个 \(dis\)，一定不会被其他 \(dis\) 继续转移而来。我们注意到这个 dp 式子也是有这个特征的。说明我们是可以用 dijkstra 的！
但是我一般写的 dijkstra 板子放在这里并不是完全有道理的。在这里就可以体现出来。我的板子修改之后长这样：
#include<bits/stdc++.h>
using namespace std;
vector<int> g[200100];
vector<int> rv[200100];
int out[200100];
int dp[200100];
bool vis[200100];
signed main(){
int n,m;cin>>n>>m;
f(i,1,m){
int u,v;cin>>u>>v;
g[u].push_back(v);rv[v].push_back(u);
}
f(i, 1, n) dp[i] = inf;
priority_queue<pii> q;
q.push({ 0,n});
while(!q.empty()) {
pii k = q.top();int d=-k.first, x=k.second;q.pop();
out[x]++;
vis[x] = 1;
if(dp[x] > d+g[x].size()-out[x]+1){
dp[x] = d+g[x].size()-out[x]+1;
for(int i : rv[x]){
if(vis[i] )continue;
q.push({ -dp[x],i});
}
}
}
cout<<dp[1]<<endl;
这个代码 wa 6 了。仔细思考，发现这个 \(out\) 数组更新的有点问题。
\(out\) 数组，指的是对于一个邻点，如果用现在的这个点来走，可以不删多少条边。可以不删的边，唯一的判断条件应当是 \(dp\) 值比它小的。而我们更新过程中，应当在任何一条边找到它的时候更新。由于更新先后，\(dp\) 是单调递增的，并且一旦启用更新，由贪心证明得知是不会更新第二次的，因此每条边只会更新一次。应该是这样的：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
vector<int> g[200100];
vector<int> rv[200100];
int out[200100];
int dp[200100];
bool vis[200100];
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n,m;cin>>n>>m;
f(i,1,m){
int u,v;cin>>u>>v;
g[u].push_back(v);rv[v].push_back(u);
}
// g[n].push_back(0);
f(i, 1, n) dp[i] = inf;
dp[n] = 0;
priority_queue<pii> q;
q.push({0,n});
while(!q.empty()) {
pii k = q.top();int d=-k.first, x=k.second;q.pop();
if(d != dp[x]) {
continue;
}
// cout << d << " " << x << " " << dp[x] << endl;
for(int v : rv[x]) {
out[v] ++;
if(dp[v] > dp[x] + g[v].size() - out[v] + 1) {
dp[v] = dp[x] + g[v].size() - out[v] + 1;
// cout << x << " " << v << " " << g[v].size() << " " << out[v] << " " << dp[v] << endl;
q.push({-dp[v], v});
}
}
}
cout<<dp[1]<<endl;
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
【学到了什么】
应该认真分析写的每一步，而不是糊里糊涂地直接写下去。要有“枚举思路”的思想，既然没有到达一眼就看出思想的功力，就考虑枚举思路，反正就那么几个。