PAT甲级1111

题目链接

【题意】

输入当前的位置和目的地，在线地图可以推荐几条路径。现在你的任务是向用户推荐两条路径：一条最短，另一条最快，输入确保有解。

【输入格式】

单组输入，第一行分别给出两个正整数N（2 <= N <= 500）和M，分别是地图上的结点总数和街道的数量。然后按照M行，每一行都按照以下格式描述一条街道：

起点 终点 单程 长度 时间

其中起点和终点是街道两端的结点编号（从0到N-1）如果街道从起点到终点为单向，则单程值为1，否则为0。长度是街道的长度，时间是通过街道所需的时间。

最后给出一对源和目的地。

【输出格式】

首先以最短距离距离D打印从源到目的地的最短路径，格式为：

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

然后在下一行打印总时间为T的最快路径，格式为：

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

在最短路径不唯一的情况下，输出最短路径中最快的路径，这是保证唯一的。如果最快的路径不是唯一的，则输出通过最少路口的路段，这也是保证唯一的。

如果最短路径和最快路径相同，则按以下格式将它们打印在一行中，格式为：

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

【思路】

图论中的最短路径问题，分别把距离和时间看成图中边的权值，然后用Dijkstra算法求源点到其它各点的最短路径，同时记录每个点的前驱点。因为根据题中的描述，不论是距离最短的最短路径还是时间最短的最短路径，都不一定是唯一的，所以都需要再额外增加一个限制条件。对于距离最短路径来说，用数组d对距离做松弛操作，如果最短路相同，那么再用一个数组t对时间做松弛操作，即在最短路相同的前提下进一步求最短时间。同理，对于时间最短路径来说也是一样，不过这一次是用数组d对时间做松弛操作，用数组t对到达每个结点的最短路所经过结点的个数做松弛操作，即在时间最短的前提下保证经过的结点数最少。

#include
    
     using namespace std;const int inf = 0x3f3f3f3f;const int maxn = 550;struct Edge {    int from, to, dist, other;    Edge(int f, int t, int d, int o) :from(f), to(t), dist(d), other(o) {}};struct HeapNode {    int d, u;    HeapNode(int dd, int uu) :d(dd), u(uu) {}    bool operator<(const HeapNode& rhs)const {        return d > rhs.d;    }};struct Dijkstra {    int n, m;    vector
     
       edges;    vector
      
        g[maxn];    vector
       
         path;    bool done[maxn];    int d[maxn];    int t[maxn];    int p[maxn];    void init(int n) {        path.clear();        this->n = n;        for (int i = 0; i < n; ++i) g[i].clear();        edges.clear();    }    void add(int from, int to, int dist, int other) {        edges.push_back(Edge(from, to, dist, other));        m = edges.size();        g[from].push_back(m - 1);    }    void dijkstra_Distance(int s) {
   //计算最短距离        priority_queue
        
          que;        for (int i = 0; i < n; ++i) { d[i] = inf; t[i] = inf; }        d[s] = 0;        t[s] = 0;        memset(done, 0, sizeof(done));        que.push(HeapNode(0, s));        while (!que.empty()) {            HeapNode x = que.top();            que.pop();            int u = x.u;            if (done[u]) continue;            done[u] = true;            for (int i = 0; i < g[u].size(); ++i) {                Edge& e = edges[g[u][i]];                if (d[e.to] > d[u] + e.dist) {                    d[e.to] = d[u] + e.dist;                    t[e.to] = t[u] + e.other;                    p[e.to] = g[u][i];                    que.push(HeapNode(d[e.to], e.to));                }                else if (d[e.to] == d[u] + e.dist && t[e.to] > t[u] + e.other) {                    t[e.to] = t[u] + e.other;                    p[e.to] = g[u][i];                }            }        }    }    void dijkstra_Time(int s) {
   //计算最短时间        priority_queue
         
           que; for (int i = 0; i < n; ++i) { d[i] = inf; t[i] = inf; } d[s] = 0; t[s] = 0; memset(done, 0, sizeof(done)); que.push(HeapNode(0, s)); while (!que.empty()) { HeapNode x = que.top(); que.pop(); int u = x.u; if (done[u]) continue; done[u] = true; for (int i = 0; i < g[u].size(); ++i) { Edge& e = edges[g[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; t[e.to] = t[u] + 1; p[e.to] = g[u][i]; que.push(HeapNode(d[e.to], e.to)); } else if (d[e.to] == d[u] + e.dist && t[e.to] > t[u] + 1) { t[e.to] = t[u] + 1; p[e.to] = g[u][i]; } } } } void print(int x) { //递归记录以x为终点的最短路径 if (d[x] == 0) { path.push_back(x); return; } Edge& e = edges[p[x]]; print(e.from); path.push_back(x); }};int n, m;Dijkstra Distance, Time;int main() { scanf("%d%d", &n, &m); Distance.init(n); Time.init(n); for (int i = 0; i < m; ++i) { int from, to, oneway, length, time; scanf("%d%d%d%d%d", &from, &to, &oneway, &length, &time); if (oneway == 1) { Distance.add(from, to, length, time); Time.add(from, to, time, length); } else { Distance.add(from, to, length, time); Distance.add(to, from, length, time); Time.add(from, to, time, length); Time.add(to, from, time, length); } } int s, t; scanf("%d%d", &s, &t); Distance.dijkstra_Distance(s); Time.dijkstra_Time(s); Distance.print(t); Time.print(t); bool same = true; if (Distance.path.size() != Time.path.size()) same = false; else { for (int i = 0; i < Distance.path.size(); ++i) { if (Distance.path[i] != Time.path[i]) { same = false; break; } } } if (same) { printf("Distance = %d; Time = %d: ", Distance.d[t], Time.d[t]); printf("%d", Distance.path[0]); for (int i = 1; i < Distance.path.size(); ++i) { printf(" -> %d", Distance.path[i]); } } else { printf("Distance = %d: ", Distance.d[t]); printf("%d", Distance.path[0]); for (int i = 1; i < Distance.path.size(); ++i) { printf(" -> %d", Distance.path[i]); } printf("\nTime = %d: ", Time.d[t]); printf("%d", Time.path[0]); for (int i = 1; i < Time.path.size(); ++i) { printf(" -> %d", Time.path[i]); } printf("\n"); } return 0;}