ABC164_E 分层图

二维费用Dijkstra

在每个点要考虑点权\(c\)影响当前可达的位置以及当前点的转换代价为\(d\)
从上限看，如果超过了\(lim = 50 * (n - 1)\)最大银币需求那么就是简单跑一遍\(Dijkstra\)
所以要考虑的点就是当前节点携带的银币总量，记录一下这个状态作为\(dis[j]\)把问题化成我们常见的模型，用来跑朴素的\(Dijkstra\)，不断"绕圈"并且把状态截止到\(dis[lim]\)停下.
边数\(E = n\cdot (lim + 1) + 2m\cdot (lim + 1),\)点数\(V = n\cdot (lim + 1)\)。
跑一遍\(Dijkstra\)的复杂度是\(O((V + E)logV)\)，足够。
具体的代码细节会注释一下
[code]#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[N][lim + 5], c[N], d[N];bool vis[N][lim + 5];vector g[N];void solve() {  cin >> n >> m >> s;  for (int i = 1; i > u >> v >> coin >> w;    g.push_back({v, coin, w});    g[v].push_back({u, coin, w});  }  for (int i = 1; i > c >> d;  }  for (int i = 1; i  lim) {      ncoin = lim;    }    if (dis[ncoin] > dist + d) {      dis[ncoin] = dist + d;      hp.push({u, ncoin, dis[ncoin]});    }   //正常跑Dijkstra   for (auto [v, cost, w] : g) {      if (cost > coin)        continue;      int ncoin = coin - cost;      if (dis[v][ncoin] > dist + w) {        dis[v][ncoin] = dist + w;        hp.push({v, ncoin, dis[v][ncoin]});      }    }  }  for (int i = 2; i