1601. Online map

Original question transmission: AcWing 1601. Online map

Enter our current location and destination, and the online map can recommend some routes.

Now your job is to recommend two routes to users: one is the shortest route and the other is the fastest route.

Ensure that there is at least one route between the two places for any inquiry.

Input format

The first line contains two integers N N N and M M M. Indicates that there are in the map N N N intersections (No 0 ∼ N − 1 0 \sim N-1 0 ∼ N − 1) and M M M streets.

next M M M lines, each line describes a street, and the format is as follows:

V1 V2 one-way length time

V1 and V2 are the numbers of two intersections, indicating that there is a street between the two intersections. If one-way is 1 1 1 means that this street is a one-way street and can only go from V1 to V2. If yes 0 0 0 indicates a two-way street, which can pass freely. Length is the length of the street and time is the time spent passing through the street.

The last line will give the numbers of the starting and ending intersections.

Output format

The first line outputs the route with the shortest distance and outputs the shortest distance D D D. The format is as follows:

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

The second line outputs the fastest route and the shortest time T T T. The format is as follows:

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

If the shortest route is not unique, the route with the shortest time is output (ensure uniqueness).

If the fastest route is not unique, the route with the least intersection will be output (ensure uniqueness).

If the intersection sequence of the shortest route and the fastest route is exactly the same, output the two information in one line in the following format:

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

Data range

2 ≤ N ≤ 500 2 \le N \le 500 2≤N≤500 ,
1 ≤ M ≤ N ( N − 1 ) 2 1 \le M \le \frac{N(N-1)}{2} 1≤M≤2N(N−1)​ ,
The length and time of each road shall not exceed 1000 1000 1000 .
Duplicate streets may occur between any two intersections. (this is different from the official website)

Input example 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

Output example 1:

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

Input example 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

Output example 2:

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

Idea:

Twice dijkstra algorithm, different keywords to get the shortest route and the fastest route.

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, m, S, D;
int d1[N][N], d2[N][N];
int dist1[N], dist2[N], pre[N];
bool st[N];

pair<int, string> dijkstra(int d1[][N], int d2[][N], int type)
{
	memset(dist1, 0x3f, sizeof dist1);
	memset(dist2, 0x3f, sizeof dist2);
	memset(st, 0, sizeof st);
	dist1[S] = dist2[S] = 0;
	for(int i = 0; i < n; i++)
	{
		int t = -1;
		for(int j = 0; j < n; j++)
			if(!st[j] && (t == -1 || dist1[t] > dist1[j]))
				t = j;
		st[t] = true;
		for(int j = 0; j < n; j++)
		{
			int w;
			
			if(type == 0)
				w = d2[t][j];
			else
				w = 1;
			if(dist1[j] > dist1[t] + d1[t][j])
			{
				dist1[j] = dist1[t] + d1[t][j];
				dist2[j] = dist2[t] + w;
				pre[j] = t;
			}
			else if(dist1[j] == dist1[t] + d1[t][j])
			{
				if(dist2[j] > dist2[t] + w)
				{
					dist2[j] = dist2[t] + w;
					pre[j] = t;
				}
			}
		}
	}
	
	vector<int> path;
	for(int i = D; i != S; i = pre[i])
		path.push_back(i);
		
	pair<int, string> res;
	res.first = dist1[D];
	res.second = to_string(S);
	for(int i = path.size() - 1; i >= 0; i--)
		res.second += " -> " + to_string(path[i]);
	return res;
}

int main()
{	
	cin >> n >> m;
	memset(d1, 0x3f, sizeof d1);
	memset(d2, 0x3f, sizeof d2);
	
	for(int i = 1; i <= m; i++)
	{
		int a, b, t, c, d;
		cin >> a >> b >> t >> c >> d;
		d1[a][b] = min(d1[a][b], c);
		d2[a][b] = min(d2[a][b], d);
		if(!t)
		{
			d1[b][a] = min(d1[b][a], c);
			d2[b][a] = min(d2[b][a], d);	
		}
	}

	cin >> S >> D;
	
	auto A = dijkstra(d1, d2, 0);
	auto B = dijkstra(d2, d1, 1);
	
	if(A.second != B.second)
	{
		cout << "Distance = " << A.first << ": " << A.second << endl;
		cout << "Time = " << B.first << ": " << B.second << endl;
	}
	else
	{
		cout << "Distance = " << A.first << "; Time = " << B.first << ": " << A.second << endl;
	}
	
	return 0;
}