原题链接
- 题意：有 (n) 个城市，它们由 (m) 条双向道路连接，保证它们能够彼此到达。第 (i) 条道路连接 (u_i,v_i) ，需要花费 (x_i) 个银币，耗费 (t_i) 秒的时间。每个城市处都有兑换银币处，第 (i) 个城市中你可以用 (1) 个金币兑换 (c_i) 个银币，可以兑换无限次，不过兑换 (1) 次需要花费 (d_i) 秒的时间。你一开始在 (1) 号城市，有 (s) 个银币和无限多的金币，求到其它城市需要耗费的最小时间。(1<=n<=50)，(1<=x_i <=50)，(1 <= t_i, c_i, s, d_i <= 10^9)
- 题解：很明显建分层图，然后跑 (dij) ，显然的是，因为 (x_i) 设定过于小，所以，分层图点的数量是 (n^3) ,需要注意的是，初期接触分层图，这个是表示了两个状态，是点和在当前点一共有的钱，这两个状态要搞成一维的才方便，但是一开始是设定的是 (x imes 2500 + money + 1) 发现有重合，所以当搞到 (x imes 5000 + money + 1) 才不会重合，这个处理不能太草率。
- 代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 99;
const ll NN = 2500;
ll pos(ll x, ll money) {
return x*2 * 2500 + money + 1;
}
struct edge {
ll v, w;
};
vector<edge>G[N];
struct Node {
ll pos, dis;
bool operator<(Node rhs)const {
return rhs.dis < dis;
}
};
priority_queue<Node>pq;
bool vis[N];
ll d[N];
void dij(ll s) {
pq.push({s, 0});
memset(d, 0x3f, sizeof d);
d[s] = 0;
while (!pq.empty()) {
auto now = pq.top();
pq.pop();
ll u = now.pos;
if (vis[u])continue;
vis[u] = 1;
for (auto e:G[u]) {
if (d[e.v] > d[u] + e.w) {
d[e.v] = d[u] + e.w;
pq.push({e.v, d[e.v]});
}
}
}
}
void add(ll u, ll v, ll w) {G[u].push_back({v, w});}
ll co[N], dd[N];
void solve() {
ll n, m, kk;
cin >> n >> m >> kk;
for (ll i = 1; i <= m; i++) {
ll u, v, c, t;
cin >> u >> v >>c >> t;
for (ll j = c; j <= NN; j++ ) {
add(pos(u, j), pos(v, j - c), t);
add(pos(v, j), pos(u, j - c), t);
}
}
for (ll i = 1; i <= n; i++) {
cin >> co[i] >> dd[i];
for (ll j = 0; j + co[i] <= NN; j++) {
add(pos(i, j), pos(i, j + co[i]), dd[i]);
}
}
dij(pos(1, min(NN, kk)));
for (ll i = 2; i <= n; i++) {
ll ans = d[pos(i, 0)];
for (ll j = 0; j <= NN; j++) {
ans = min(d[pos(i, j)], ans);
}
cout << ans << endl;
}
}
signed main() {
ll t = 1;
while (t--) solve();
return 0;
}