求卡常
查看原帖
求卡常
718017
Dream__maker楼主2025/7/3 11:23

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;
}
2025/7/3 11:23
加载中...