1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/* https://arena.olimpiici.com/#/catalog/756/problem/101958 */
#include <iostream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct Path {
unsigned long long b;
unsigned long long s;
unsigned long long g;
unsigned long long r;
};
int main() {
unsigned long long N, M, S;
cin >> N >> M >> S;
vector<vector<Path>> crossroads(N+1);
for (long long i = 0; i < M; i++) {
unsigned long long ai, bi, si, gi, ri;
cin >> ai >> bi >> si >> gi >> ri;
crossroads[ai].push_back({ bi, si, gi, ri });
crossroads[bi].push_back({ ai, si, gi, ri });
}
// Dijkstra
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
vector<long> dist(N+1, -1);
vector<bool> visited(N+1, false);
q.push({ S, 1 });
while (!q.empty()) {
long long currTime = q.top().first;
long long currNode = q.top().second;
q.pop();
visited[currNode] = true;
for (Path& p : crossroads[currNode]) {
unsigned long long waitingTime = (currTime % (p.g + p.r) < p.g) ? 0 : p.g + p.r - (currTime % (p.g + p.r));
if (!visited[p.b] && (dist[p.b] < 0 || currTime + p.s + waitingTime < dist[p.b])) {
dist[p.b] = currTime + p.s + waitingTime;
q.push({ dist[p.b], p.b });
}
}
}
for (long long i = 2; i <= N; i++) {
cout << dist[i] << " ";
}
}
|
