Skip to content

Latest commit

 

History

History
104 lines (93 loc) · 4 KB

1111. Online Map.md

File metadata and controls

104 lines (93 loc) · 4 KB

pat 甲级 1111. Online Map

题意概述

输入始发地和目的地，向用户推荐两条路径：一条是最短路径，另一条是最快路径。保证路径一定存在。

输入输出格式

输入第一行给出两个正整数 N、M，分别是地图上街道交叉点的总数、街道数。接下来 M 行，每行以v1 v2 one-way length time的格式描述一条街道。其中，v1 和 v2 是街道两端的索引（从 0 到 N-1），one-way 为 1，表示街道是从 v1 到 v2 的单向路；否则，表示街道是双向路；length 是街道的长度；time 就是通过街道的时间。最后一行给出了始发地和目的地。

对于每种情况，首先以Distance = D: source -> v1 -> ... -> destination格式打印距离 D 的从源到目的地的最短路径。然后在下一行中以Time = T: source -> w1 -> ... -> destination格式打印最快的路径。如果最短路径不是唯一的，请输出最短路径中最快的一条，保证这样的路径是唯一的。如果最快的路径不是唯一的，则输出经过最少交叉点的那条，保证这样的路径是唯一的。如果最短路径和最快路径相同，则以Distance = D; Time = T: source -> u1 -> ... -> destination格式将它们打印在一行中。

数据规模

$$2≤N≤500$$

算法设计

用两次 Dijkstra+DFS 算法求出最短路径和最快路径，为了方便编码我在 Dijkstra 和 DFS 算法的参数中均有 index 这个参数，index==0 时表示求的是最短路径；index==1 时表示求的是最快路径。将两个路径存储在两个 vector 中，为了方便编码，也可以定义一个长度为 2 的 vector 的数组，下标为 0 存储最短路径，下标为 1 存储最快路径，比较两个路径，根据是否完全一致按要求输出。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
using agg3 = array<gg, 3>;
const gg MAX = 505;
struct Edge {
    gg to, cost, time;
    Edge(gg t, gg c, gg ti) : to(t), cost(c), time(ti) {}
};
vector<vector<Edge>> graph(MAX);
vector<gg> dis(MAX), dis2(MAX), past(MAX, -1);
vector<vector<gg>> path(2);
void Dijkstra(gg s, gg index) {
    priority_queue<agg3, vector<agg3>, greater<agg3>> pq;
    fill(dis.begin(), dis.end(), INT_MAX);
    fill(dis2.begin(), dis2.end(), INT_MAX);
    dis[s] = dis2[s] = 0;
    pq.push({0, 0, s});
    while (not pq.empty()) {
        auto p = pq.top();
        pq.pop();
        if (dis[p[2]] != p[0]) {
            continue;
        }
        for (auto& e : graph[p[2]]) {
            gg v1 = index == 0 ? e.cost : e.time, v2 = index == 0 ? e.time : 1;
            if (tie(dis[e.to], dis2[e.to]) > make_tuple(p[0] + v1, p[1] + v2)) {
                dis[e.to] = p[0] + v1;
                dis2[e.to] = p[1] + v2;
                past[e.to] = p[2];
                pq.push({dis[e.to], dis2[e.to], e.to});
            }
        }
    }
}
void dfs(gg v, gg index) {
    if (v == -1) {
        return;
    }
    dfs(past[v], index);
    path[index].push_back(v);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi;
    cin >> ni >> mi;
    while (mi--) {
        gg a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        graph[a].push_back(Edge(b, d, e));
        if (c == 0) {
            graph[b].push_back(Edge(a, d, e));
        }
    }
    gg s, e;
    cin >> s >> e;
    Dijkstra(s, 0);
    dfs(e, 0);
    gg len = dis[e];
    Dijkstra(s, 1);
    dfs(e, 1);
    gg time = dis[e];
    if (path[0] == path[1]) {
        cout << "Distance = " << len << "; Time = " << time << ": ";
        for (gg i = 0; i < path[0].size(); ++i) {
            cout << (i == 0 ? "" : " -> ") << path[0][i];
        }
    } else {
        cout << "Distance = " << len << ": ";
        for (gg i = 0; i < path[0].size(); ++i) {
            cout << (i == 0 ? "" : " -> ") << path[0][i];
        }
        cout << "\nTime = " << time << ": ";
        for (gg i = 0; i < path[1].size(); ++i) {
            cout << (i == 0 ? "" : " -> ") << path[1][i];
        }
    }
    return 0;
}