[luogu P1266]速度限制（二维spfa）

Posted on | In ,
luogu P1266

题目

描述

在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地A和B，最多只有一条道路从A连接到B。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。

输入

第一行是3个整数N，M和D(2<＝N<=150)，表示道路的数目，用0..N-1标记。M是道路的总数，D表示你的目的地。

接下来的M行，每行描述一条道路，每行有4个整数A(0≤A<N)，B(0≤B<N)，V(0≤V≤500)and L(1≤L≤500)，这条路是从A到B的，速度限制是V，长度为L。如果V是0，表示这条路的限速未知。

如果V不为0，则经过该路的时间T=L/V。否则T=L/Vold，Vold是你到达该路口前的速度。开始时你位于0点，并且速度为70。

输出

输出文件仅一行整数，表示从0到D经过的城市。

输出的顺序必须按照你经过这些城市的顺序，以0开始，以D结束。仅有一条最快路线。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

输出样例

1
0 5 2 3 1

解题思路

设 $tim[i][j]$ 表示到达 $i$ 点时速度为 $j$ 的最短时间，以之代替 $dis[i]$ 跑 spfa 即可。

（ps:用了 map 和 pair 果真有点慢…）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fir first
#define sec second

#define fo0(i,a,b) for(int i=(a);i<(b);i++)
#define fo1(i,a,b) for(int i=(a);i<=(b);i++)
#define fd0(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define fd1(i,a,b) for(int i=(a);i>=(b);i--)
#define mset(a,b) memset(a,(b),sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

template<typename T> inline void in(T &x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9')
{if(ch=='-')fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T> void out(T x){if(x<0){putchar('-');x=-x;}if(x/10)out(x/10);putchar(x%10+'0');}
template<typename T> inline void outln(T x){out(x);putchar(10);}
template<typename T> inline void outsp(T x){out(x);putchar(' ');}
template<typename T> inline T gcd(T a, T b){T t;if(a>b){while(b){
t=b;b=a%b;a=t;}return a;}else{while(a){t=a;a=b%a;b=t;}return b;}}
template<typename T> inline T lcm(T a, T b){return a/gcd(a,b)*b;}

const int N = 155;

int n, m, d, u, v, w, p;

struct Edge{
	int nxt, from, to, v, len;
}edge[N*N];
int head[N], edgeNum;
void addEdge(int from, int to, int v, int len){
	edge[++edgeNum] = (Edge){head[from], from, to, v, len};
	head[from] = edgeNum;
}

double tim[N][505];
bool inq[N][505];
map<pii, pii> pre;
void spfa(){
	queue<pii> q;
	q.push({1, 70});
	inq[1][70] = 1;
	tim[1][70] = 0;
	pre[{1, 70}] = {0, 0};
	while(!q.empty()){
		pii cur = q.front(); q.pop(); inq[cur.fir][cur.sec] = 0;
		int x = cur.fir, sp = cur.sec;
		for(int i = head[x]; i; i = edge[i].nxt){
			if(edge[i].v == 0){
				if(tim[edge[i].to][sp] > tim[x][sp] + (double)edge[i].len / sp){
					tim[edge[i].to][sp] = tim[x][sp] + (double)edge[i].len / sp;
					pre[{edge[i].to, sp}] = {x, sp};
					if(!inq[edge[i].to][sp]){
						q.push({edge[i].to, sp});
						inq[edge[i].to][sp] = 1;
					}
				}
			}
			else{
				if(tim[edge[i].to][edge[i].v] > tim[x][sp] + (double)edge[i].len / edge[i].v){
					tim[edge[i].to][edge[i].v] = tim[x][sp] + (double)edge[i].len / edge[i].v;
					pre[{edge[i].to, edge[i].v}] = {x, sp};
					if(!inq[edge[i].to][edge[i].v]){
						q.push({edge[i].to, edge[i].v});
						inq[edge[i].to][edge[i].v] = 1;
					}
				}
			}
		}
	}
}

int main(){
	in(n); in(m); in(d); d++;
	fo1(i, 1, m){
		in(u); in(v); in(w); in(p);
		addEdge(u+1, v+1, w, p);
	}
	fo1(i, 1, n)
		fo1(j, 1, 500)
			tim[i][j] = 1e9;
	spfa();
	double ans = 1e9;
	pii mark;
	fo1(i, 1, 500){
		if(ans > tim[d][i]){
			ans = tim[d][i];
			mark = {d, i};
		}
	}
	stack<int> sta;
	while(mark.fir){
		sta.push(mark.fir);
		mark = pre[mark];
	}
	while(!sta.empty()){
		outsp(sta.top()-1);
		sta.pop();
	}
	return 0;
}