1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4  5 using namespace std; 6  7 const int MAXN = 151; 8 int n, m, d, cnt; 9 int head[MAXN], to[MAXN * MAXN], next[MAXN * MAXN], spd[MAXN * MAXN], lon[MAXN * MAXN], pr[MAXN][510], ps[MAXN][510];10 double dis[MAXN][510], ans = 12345678;11 bool vis[MAXN][510];12 queue < pair <int, int> > q;13 pair <int, int> x;14 15 inline void add(int x, int y, int v, int l)16 {17     to[cnt] = y;18     spd[cnt] = v;19     lon[cnt] = l;20     next[cnt] = head[x];21     head[x] = cnt++;22 }23 24 inline void spfa()25 {26     int i, j, u, v, s, p;27     memset(dis, 70, sizeof(dis));28     q.push(make_pair(0, 70));29     dis[0][70] = 0;30     while(!q.empty())31     {32         x = q.front();33         q.pop();34         u = x.first;35         s = x.second;36         vis[u][s] = 0;37         for(i = head[u]; i != -1; i = next[i])38         {39             v = to[i];40             p = spd[i] == 0 ? s : spd[i];41             if(dis[v][p] > dis[u][s] + 1.0 * lon[i] / p)42             {43                 dis[v][p] = dis[u][s] + 1.0 * lon[i] / p;44                 pr[v][p] = u;45                 ps[v][p] = s;46                 if(!vis[v][p])47                 {48                     vis[v][p] = 1;49                     q.push(make_pair(v, p));50                 }51             }52         }53     }54 }55 56 inline void print(int u, int pos)57 {58     if(pr[u][pos] != -1) print(pr[u][pos], ps[u][pos]);59     printf("%d ", u);60 }61 62 int main()63 {64     int i, x, y, v, l, pos;65     scanf("%d %d %d", &n, &m, &d);66     memset(pr, -1, sizeof(pr));67     memset(ps, -1, sizeof(ps));68     memset(head, -1, sizeof(head));69     for(i = 1; i <= m; i++)70     {71         scanf("%d %d %d %d", &x, &y, &v, &l);72         add(x, y, v, l);73     }74     spfa();75     for(i = 0; i <= 500; i++)76         if(ans > dis[d][i])77             ans = dis[d][i], pos = i;78     print(d, pos);79     return 0;80 }