数据结构与算法复习：第三十五弹

1. 一些历史遗留问题

1111 Online Map

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time
1

where V1 and V2 are the indices (from 0 to N−1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> ... -> destination
1

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> ... -> destination
1

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

Distance = D; Time = T: source -> u1 -> ... -> destination
1

Sample Input 1:

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Sample Output 1:

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
1
2

Sample Input 2:

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
1
2
3
4
5
6
7
8
9
10
11

Sample Output 2:

Distance = 3; Time = 4: 3 -> 2 -> 5
1

比较典型的Dijkstra+DFS找到最短路径的模板题
_{虽然不知道之前做的时候为什么卡在第二个测试点}
以下是订正后的AC代码，找最短和最快路径其实套路是一样的，主要是最后确定路径的时候前者需要时间最小、后者需要经过的结点数最少，以及输出答案的时候注意格式问题即可

#include
using namespace std;
//推荐两条路：一条最短(最快)，一条最快(最少的中转站)
const int inf=INT_MAX;
int N,M,v1,v2,one_way,ll,tt;
int st,ed;
int min_time=inf,min_trans=inf;
vector<vector<int> >d,t,pre;//路程，时间 
vector<int>s_path,f_path;
/*找到最短的路*/
void dfs_shortest(int id,vector<int>temp){
	temp.push_back(id);
	if(id==st){
		int temp_time=0;
		int len=temp.size();
		for(int i=len-1;i>=1;i--){
			temp_time+=t[temp[i]][temp[i-1]];
		}
		if(temp_time<min_time){
			min_time=temp_time;
			s_path=temp;
		}
	}else{
		for(int i=0;i<pre[id].size();i++){
			dfs_shortest(pre[id][i],temp);
		}
	}
	temp.pop_back();
}
int findShortest(){
	vector<int>dis(N,inf);
	vector<bool>vis(N,false);
	pre.resize(N);
	dis[st]=0;
	while(1){
		int u=-1;
		int min_dis=inf;
		for(int i=0;i<N;i++){
			if(!vis[i]&&min_dis>dis[i]){
				min_dis=dis[i];
				u=i;
			}
		}
		if(u==-1){
			break;
		}
		vis[u]=true;
		for(int v=0;v<N;v++){
			if(!vis[v]){
				if(d[u][v]!=inf){
					if(dis[u]+d[u][v]<dis[v]){
						dis[v]=dis[u]+d[u][v];
						pre[v].clear();
						pre[v].push_back(u);
					}else if(dis[u]+d[u][v]==dis[v]){
						pre[v].push_back(u);
					}
				}
			}
		}
	}
	vector<int>temp;
	dfs_shortest(ed,temp);
	pre.clear(); 
	return dis[ed];
}
/*找到最快的路*/
void dfs_fastest(int id,vector<int>temp){
	temp.push_back(id);
	if(id==st){
		int len=temp.size();
		if(len<min_trans){
			min_trans=len;
			f_path=temp;
		}
//		printf("=====\n");
//		for(int i=0;i
//			printf("%d ",temp[i]);
//		}
//		printf("\n====\n");
	}else{
		for(int i=0;i<pre[id].size();i++){
			dfs_fastest(pre[id][i],temp);
		}
	}
	temp.pop_back();
}
int findFastest(){
	vector<int>dis(N,inf);
	vector<bool>vis(N,false);
	pre.resize(N);
	dis[st]=0;
	while(1){
		int u=-1;
		int min_dis=inf;
		for(int i=0;i<N;i++){
			if(!vis[i]&&min_dis>dis[i]){
				min_dis=dis[i];
				u=i;
			}
		}
		if(u==-1){
			break;
		}
		vis[u]=true;
		for(int v=0;v<N;v++){
			if(!vis[v]){
				if(t[u][v]!=inf){
					if(dis[u]+t[u][v]<dis[v]){
						dis[v]=dis[u]+t[u][v];
						pre[v].clear();
						pre[v].push_back(u);
					}else if(dis[u]+t[u][v]==dis[v]){
						pre[v].push_back(u);
					}
				}
			}
		}
	}
	vector<int>temp;
	dfs_fastest(ed,temp);
	pre.clear(); 
	return dis[ed];
}
int main(){
	scanf("%d%d",&N,&M);
	d.resize(N);
	t.resize(N);
	for(int i=0;i<N;i++){
		d[i].resize(N);
		t[i].resize(N);
		fill(d[i].begin(),d[i].end(),inf);
		fill(t[i].begin(),t[i].end(),inf);
		d[i][i]=0;t[i][i]=0;
	}
	for(int i=0;i<M;i++){
		scanf("%d%d%d%d%d",&v1,&v2,&one_way,&ll,&tt);
		d[v1][v2]=min(d[v1][v2],ll);
		t[v1][v2]=min(t[v1][v2],tt);
		if(one_way==0){
			d[v2][v1]=d[v1][v2];
			t[v2][v1]=t[v1][v2];
		}
	}
	scanf("%d%d",&st,&ed);
	int f=findFastest();
	int s=findShortest();
	if(s_path==f_path){
		printf("Distance = %d; Time = %d: ",s,f);
		int len=s_path.size();
		for(int i=len-1;i>=0;i--){
			if(i!=len-1){
				printf(" -> ");
			}
			printf("%d",s_path[i]);
		}
	}else{
		printf("Distance = %d: ",s);
		int len=s_path.size();
		for(int i=len-1;i>=0;i--){
			if(i!=len-1){
				printf(" -> ");
			}
			printf("%d",s_path[i]);
		}
		printf("\nTime = %d: ",f);
		len=f_path.size();
		for(int i=len-1;i>=0;i--){
			if(i!=len-1){
				printf(" -> ");
			}
			printf("%d",f_path[i]);
		}
	}
	return 0;
} 
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176