考虑倒着 dp。设 表示从 到 最优策略下最多走多少步。考虑到若要保证从 点走到 点，那么需要先把所有比走到 点更差的边全部断掉，才能保证从 走到 一定为最差情况。那么 dp 就是：初始条件为 ，转移对于每一个 ，都有 ，其中 表示从 点走到 点最少要断多少条 点的出边。
是容易计算的，显然有：
于是可以直接暴力转移，时间复杂度为 。考虑一个很厉害的优化：考虑到 ，因此图中不存在负权边和负权环，考虑用 dijkstra 维护，每一次从堆顶端取出当前 权值最小的结点。此时可以证明 的值一定单调不递增，且每一次递减的值不会超过 ，而且还可以发现初始 的值其实就是 。因此可以直接简单的在 dijkstra 的过程中暴力维护，时间复杂度为 ，可以通过。
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200100;
vector<int> adj[N];
int deg[N], dis[N];
struct Node {
int dis, u;
bool operator<(const Node &r) const {
return dis > r.dis;
}
};
signed main() {
cin.tie(0)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
adj[b].emplace_back(a);
++deg[a];
}
priority_queue<Node> q;
memset(dis, 0x3f, sizeof dis);
q.push({dis[n] = 0, n});
while (q.size()) {
auto [Dis, u] = q.top();
q.pop();
if (dis[u] >= Dis) {
for (auto &v : adj[u])
if (dis[v] > dis[u] + deg[v]) q.push({dis[v] = dis[u] + deg[v]--, v});
else --deg[v];
}
}
cout << dis[1] << '\n';
return 0;
}
喜欢的话，留下你的评论吧～