素晴らしき日々

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
using PII = pair<int, int>;
5
using PDII = pair<double,PII>;
6

7
const int N = 160,INF = 1e9, M = N * N * 2;
8

9
/*
10
本题出现的一大难点：
11
    1. 有速度限制，并且部分没有速度的路径需要用上一段结束的速度并保持（这里有点像动态规划转移的思想）
12

13

14
*/
15

16
class cmp{
17
public:
18
    bool operator()(PDII a, PDII b){
19
        return a.first > b.first;
20
    }
21
};
22

23
int n, m;
24
int h[N], ne[M], e[M], v[M], s[M], idx;
25
int st[N][510]; //表示 到 i 点速度 j 是否被访问过
26
double dist[N][510]; // 表示 到 i 点速度 j 的最短时间
27
PII last[N][510];
28

29
void add(int a, int b, int c, int d){
30
    e[idx] = b, v[idx] = c, s[idx] = d, ne[idx] = h[a], h[a] = idx++;
31
}
32

33
void show(int u, int v){
34
    if(u == 0) return;
35
    show(last[u][v].first, last[u][v].second);
36
    cout << " " << u ;
37
}
38

39
void dijk(int ed){
40
    for(int i = 0; i <= n; i++){
41
        for(int j = 0; j < 510; j++){
42
            dist[i][j] = INF;
43
        }
44
    }
45
    dist[0][70] = 0;
46
    priority_queue<PDII, vector<PDII>, cmp> heap;
47
    heap.push({0, {0, 70}});
48
    while(heap.size()){
49
        auto t = heap.top();
50
        heap.pop();
51
        int ver = t.second.first, speed = t.second.second;
52
        double dis = t.first;
53
        if(st[ver][speed]) continue;
54
        st[ver][speed] = 1;
55
        for(int i = h[ver]; i != -1; i = ne[i]){
56
            int j = e[i];
57
            int nv = v[i], ns = s[i];
58
            if(nv){
59
                if(dist[j][nv] > dis + ns * 1.0 / nv){
60
                    dist[j][nv] = dis + ns * 1.0 / nv;
61
                    last[j][nv] = {ver, speed};
62
                    heap.push({dist[j][nv], {j, nv}});
63
                }
64
            }else{
65
                nv = speed;
66
                if(dist[j][nv] > dis + ns * 1.0 / nv){
67
                    dist[j][nv] = dis + ns * 1.0 / nv;
68
                    last[j][nv] = {ver, speed};
69
                    heap.push({dist[j][nv], {j, nv}});
70
                }
71
            }
72
        }
73
    }
74

75
    int mv = 0;
76
    for(int i = 0; i < 510; i++){
77
        if(dist[ed][i] < dist[ed][mv]) mv = i;
78
    }
79
    //cout << mv << endl;
80
    cout << "0";
81
    show(ed, mv);
82
    cout << endl;
83
}
84

85
void solve(){
86
    int ed;
87
    memset(h, -1 ,sizeof h);
88
    cin >> n >> m >> ed;
89

90
    for(int i = 1; i <= m; i++){
91
        int a, b, c, d;
92
        cin >> a >> b >> c >> d;
93
        add(a, b, c, d);
94
        //add(b, a, c, d);
95
    }
96
    dijk(ed);
97
}
98

99
signed main(){
100
    ios::sync_with_stdio(false);
101
    cin.tie(0);
102
    cout.tie(0);
103
    int _ = 1;
104
    while(_--){
105
        solve();
106
    }
107
}