ABC164_E 分层图
二维费用Dijkstra在每个点要考虑点权\(c\)影响当前可达的位置以及当前点的转换代价为\(d\)
从上限看，如果超过了\(lim = 50 * (n - 1)\)最大银币需求那么就是简单跑一遍\(Dijkstra\)
所以要考虑的点就是当前节点携带的银币总量，记录一下这个状态作为\(dis\)把问题化成我们常见的模型，用来跑朴素的\(Dijkstra\)，不断"绕圈"并且把状态截止到\(dis\)停下.
边数\(E = n\cdot (lim + 1) + 2m\cdot (lim + 1),\)点数\(V = n\cdot (lim + 1)\)。
跑一遍\(Dijkstra\)的复杂度是\(O((V + E)logV)\)，足够。
具体的代码细节会注释一下
#include #define fi first#define se second#define endl '\n'#define pii pair#define int long longusing namespace std;using ll = long long;using LD = long double;int T;const int mod = 998244353;const ll inf = 3e18;int n, m, s;struct node {int v, coin, w;bool operator u.w; }};struct edge {int v, cost, w;};const int N = 55, lim = 2450;int dis, c, d;bool vis;vector g;void solve() {cin >> n >> m >> s;for (int i = 1; i > u >> v >> coin >> w; g.push_back({v, coin, w}); g.push_back({u, coin, w});}for (int i = 1; i > c >> d;}for (int i = 1; ilim) { ncoin = lim; } if (dis > dist + d) { dis = dist + d; hp.push({u, ncoin, dis}); } //正常跑Dijkstra for (auto : g) { if (cost > coin) continue; int ncoin = coin - cost; if (dis > dist + w) { dis = dist + w; hp.push({v, ncoin, dis}); } }}for (int i = 2; i 这个有用。 谢谢分享，辛苦了 热心回复！ 热心回复！ 感谢分享，下载保存了，貌似很强大 很好很强大我过来先占个楼 待编辑
页:
[1]