1111 Online Map (30 分)
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
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
Then in the next line print the fastest path with total time
T
:
Time = T: source -> w1 -> ... -> destination
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
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
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
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
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5
題目大意：給定一個有向有權圖，求最短路徑和最快路徑，若兩條最短路徑相同則輸出時間短的那條路徑，若兩條最快路徑相同則輸出經過的節點少的那條，若最短路徑和最快路徑相同，則輸出路徑長度、時間和路徑節點。題目裡的one-way指的是目前的兩個節點v1、v2是否為單向路徑。
思路：兩次Dijkstra即可，采用鄰接表+堆優化（使用C++的queue容器，priority_queue本質上就是一個堆，不嫌麻煩的也可以手寫堆的操作）的Dijkstra算法，題目裡面對每條路徑都有兩個優先級的要求，是以需要在struct裡面設定變量的優先級。
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#define INFI 10000
#define MaxVNum 500
using namespace std;
struct ENode {
int length = INFI, time = INFI;
} E[MaxVNum][MaxVNum];//邊
struct distNode {
int u, dist = INFI, time = INFI;
friend bool operator < (const distNode &a, const distNode &b) {
return a.dist != b.dist ? a.dist > b.dist : a.time > a.time;
}
};
struct timeNode {
int u, time = INFI, num = INFI;
friend bool operator < (const timeNode &a, const timeNode &b) {
return a.time != b.time ? a.time > b.time : a.num > b.num;
}
};
vector <int> V[MaxVNum];//頂點
int sPath[MaxVNum], fPath[MaxVNum];//分别記錄最短路徑和最快路徑
int DijkstraDis(int sour, int des, int N);
int DijkstraTime(int sour, int des, int N);
void printPath(vector <int> &v, int &size);//将逆序路徑順序輸出
int main()
{
int N, M, sour, des;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) {
int v1, v2, flag, len, time;
scanf("%d%d%d%d%d", &v1, &v2, &flag, &len, &time);
V[v1].push_back(v2);
E[v1][v2].length = len;
E[v1][v2].time = time;
if (!flag) {
V[v2].push_back(v1);
E[v2][v1].length = len;
E[v2][v1].time = time;
}
}
scanf("%d%d", &sour, &des);
int dis = DijkstraDis(sour, des, N);
int time = DijkstraTime(sour, des, N);
vector <int> ans1, ans2;
for (int x = des; x != -1; x = sPath[x])
ans1.push_back(x);
for (int x = des; x != -1; x = fPath[x])
ans2.push_back(x);
int size1 = ans1.size(), size2 = ans2.size();
bool flag = true;
if (size1 == size2) {
for (int i = 0; i < size1; i++) {
if (ans1[i] != ans2[i]) {
flag = false;
break;
}
}
}
if (size1 == size2 && flag) {
printf("Distance = %d; Time = %d:", dis, time);
printPath(ans1, size1);
}
else {
printf("Distance = %d:", dis);
printPath(ans1, size1);
printf("Time = %d:", time);
printPath(ans2, size2);
}
return 0;
}
void printPath(vector <int> &v, int &size) {
for (int i = size - 1; i >= 0; i--) {
printf(" %d", v[i]);
if (i > 0) {
printf(" ->");
}
}
printf("\n");
}
int DijkstraTime(int sour, int des, int N) {
vector <bool> collected(N, false);
vector <int> time(N,INFI), num(N,INFI);
priority_queue <timeNode> Q;
int u, w;
for (u = 0; u < N; u++)
fPath[u] = -1;
timeNode vertex;
vertex.u = sour;
vertex.time = time[sour] = 0;
vertex.num = num[sour] = 0;
Q.push(vertex);
while (!Q.empty()) {
vertex = Q.top();
Q.pop();
u = vertex.u;
collected[u] = true;
for (int i = 0; i < V[u].size(); i++) {
w = V[u][i];
if (!collected[w]) {
if (time[u] + E[u][w].time < time[w] || (time[u] + E[u][w].time == time[w] && num[u] + 1 < num[w])) {
time[w] = time[u] + E[u][w].time;
num[w] = num[u] + 1;
fPath[w] = u;
vertex.u = w;
vertex.time = time[w];
vertex.num = num[w];
Q.push(vertex);
}
}
}
}
return time[des];
}
int DijkstraDis(int sour, int des, int N) {
vector <bool> collected(N, false);
vector <int> dist(N,INFI), time(N,INFI);
priority_queue <distNode> Q;
distNode vertex;
int u, w;
for (w = 0; w < N; w++)
sPath[w] = -1;
vertex.u = sour;
vertex.dist = dist[sour] = 0;
vertex.time = time[sour] = 0;
Q.push(vertex);
while (!Q.empty()) {
vertex = Q.top();
Q.pop();
u = vertex.u;
collected[u] = true;
for (int i = 0; i < V[u].size(); i++) {
w = V[u][i];
if (!collected[w]) {
if (dist[u] + E[u][w].length < dist[w] || (dist[u] + E[u][w].length == dist[w] && time[u] + E[u][w].time < time[w])) {
dist[w] = dist[u] + E[u][w].length;
time[w] = dist[u] + E[u][w].time;
sPath[w] = u;
vertex.u = w;
vertex.dist = dist[w];
vertex.time = time[w];
Q.push(vertex);
}
}
}
}
return dist[des];
}
![STL 六大元件概要[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)