记录编号	46644	评测结果	AAAAAAAAAA
题目名称	速度限制	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.823 s
提交时间	2012-10-29 09:06:12	内存使用	4.99 MiB

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 150 + 10, L = 500 + 10;
const int M = N * N, INF = 0x7ffffff;
struct den {
    int a, b, v, l;
} e[M];
int n, m, d;
int G[N], p[N][L][2];
double f[N][L];
void print(int u, int v) {
    if(p[u][v][0] < 0) {
        printf("%d ", u);
        return;
    } print(p[u][v][0], p[u][v][1]);
    printf("%d ", u);
}
queue<pair<int, int> > q;
bool o[N][L];
void Bellman() {
    for(int i=1; i<=n; i++)
        fill(f[i], f[i]+L, INF);
    o[0][e[0].v] = 1; f[0][e[0].v] = 0;
    p[0][e[0].v][0] = p[0][e[0].v][0] = -1;
    q.push(make_pair(0, e[0].v));
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        o[x][y] = 0; int z = G[x];
        while(z > 0) {
            int b = e[z].b, v = e[z].v, l = e[z].l;
            if(!v) v = y;
            if(f[b][v] > f[x][y] + (double)l / v) {
                f[b][v] = f[x][y] + (double)l / v;
                p[b][v][0] = x, p[b][v][1] = y;
                if(!o[b][v]) {
                    q.push(make_pair(b, v));
                    o[b][v] = 1;
                }
            }
            z = e[z].a;
        }
    }
}
int main() {
    freopen("speed.in", "r", stdin);
    freopen("speed.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &d);
    fill(G, G+n+1, -1);
    for(int i=1; i<=m; i++) {
        int a, b, v, l;
        scanf("%d %d %d %d", &a, &b, &v, &l);
        e[i].b = b; e[i].v = v; e[i].l = l;
        e[i].a = G[a]; G[a] = i;
    } e[0].v = 70;
    Bellman();
    double t = f[d][1]; int j = 1;
    for(int i=2; i<=L; i++)
        if(f[d][i] < t)
            t = f[d][j = i];
    print(p[d][j][0], p[d][j][1]);
    printf("%d\n", d);
    return 0;
}