TLE on #2
卡了一上午了qwq
#include <bits/stdc++.h>
#define dd float
using namespace std;
const int N = 160, M = 23000;
int n, m, T;
dd dis[N][510];
int vis[N][510];
int fu[N][510], fv[N][510];
int head[N], nxt[M], V[M], Y[M], cnt;
dd L[M];
void addedge(int x, int y, int v, dd l)
{
cnt ++;
nxt[cnt] = head[x];
Y[cnt] = y; V[cnt] = v; L[cnt] = l;
head[x] = cnt;
}
inline void dijkstra()
{
priority_queue <pair <dd, pair <int, int> > > q;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= 500; j ++)
dis[i][j] = 1000000.0;
dis[1][70] = 0;
q.push(make_pair(0, make_pair(1, 70)));
while (!q.empty())
{
auto t = q.top();
q.pop();
dd ds = -t.first;
int u = t.second.first;
int sp = t.second.second;
if (vis[u][sp]) continue;
vis[u][sp] = 1;
for (int i = head[u]; i; i = nxt[i])
{
int yy = Y[i];
int v = V[i] ? V[i] : sp;
dd res = ds + L[i] / (1.0 * v);
if (res < dis[yy][v])
{
dis[yy][v] = res;
fu[yy][v] = u;
fv[yy][v] = sp;
}
if (!vis[yy][v]) q.push(make_pair(-dis[yy][v], make_pair(yy, v)));
}
}
}
int dl[N], ld;
int main()
{
scanf("%d%d%d",&n,&m,&T); T ++;
int x, y, v;
double l;
for (int i = 1; i <= m; i ++)
{
scanf("%d%d%d%lf",&x,&y,&v,&l);
x ++, y ++;
addedge(x, y, v, l);
}
dijkstra();
dd ans = 1000000.0;
int spd = 0;
for (int i = 1; i <= 500; i ++)
{
if (dis[T][i] < ans)
{
ans = dis[T][i];
spd = i;
}
}
int now = T;
dl[++ ld] = now;
while (now != 1)
{
dl[++ ld] = fu[now][spd];
spd = fv[now][spd];
now = dl[ld];
}
for (int i = ld; i >= 1; i --) printf("%d ", dl[i] - 1);
return 0;
}