include <bits/stdc++.h>
using namespace std;
define int long long
vector<array<int, 5>> adj[1000005];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int l, d, k, c, a, b;
cin >> l >> d >> k >> c >> a >> b;
adj[b].push_back({l, d, k, c, a});
}
auto dij =[&] (int x) {
// cerr << "OK\n";
priority_queue<pair<int, int>> q;
vector<int> dis(n + 1, 0);
vector<bool> vis(n + 1, 0);
dis[x] = 2e18;
q.push({dis[x], x});
while(q.size()) {
// cerr << "ok\n";
auto [_dis, u] = q.top();
// cerr << _dis << " " << u << endl;
q.pop();
if(vis[u]) {
continue;
}
vis[u] = 1;
for (auto [_l, _d, _k, _c, _a] : adj[u]) {
if(dis[u] - _c < _l) { //没边
continue;
}
// dis[u] - _c 是最晚到前一个地点的时间, k - 1是下限
int x = min((dis[u] - _c - _l) / _d, _k - 1) * _d + _l;
if(x > dis[_a]) {
dis[_a] = x;
q.push({dis[_a], _a});
}
}
}
for (int i = 1; i <= n - 1; i++) {
if(!dis[i]) {
cout << "Unreachable\n";
}
else {
cout << dis[i] << endl;
}
}
};
dij(n);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T--) {
solve();
}
return 0;
}
标签:int,cin,long,2024,vector,push,dis From: https://www.cnblogs.com/yyc4591/p/18050506