最短路专题1 | CodeForces 601A - 混合Dijkstra算法

前言

这个十一没有出去玩，花了一些时间在写之前提过的 markdown 编辑器，本文就是用这个编辑器写的 2333，今天准备写咱们的新专题 — 最短路。另外之前提过专题的题目主要使用 kuangbin 系列，现在改变主意了，专题题目全部使用 CodeForces 上的题目，原因主要是 POJ 等国内的 OJ 系统不能看源代码，而且题目质量稍微欠缺一些，然后没有区分度。

CodeForces 能够看到高手写的代码，题目质量相对好些，然后每个题目的难易都用 a/b/c/d 标明了。OK，开始看题。

601A. The Two Routes

In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour. 有 n 个城市，m 个双向铁轨。还有一个公路网络，对于每一对城镇 x 和 y，如果它们没有铁路，那么就一定会有公路。去一个不同的城镇，不管是铁路还是公路，都需要一个小时。

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don't make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads. 火车和汽车从 1 号站同时离开，同时开往 n。

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously. 你需要计划一下出行的方案，每一条线路都能够使用公路或者铁路。为了避免意外发生，火车和汽车不能够同时到达同一个城镇（n 除外）。

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — the number of towns and the number of railways respectively. 第一行包含 2 个整数 n 和 m，n 是城市的数量，m 是铁路的数量。

Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v). 下面的 m 行表示路线

You may assume that there is at most one railway connecting any two towns.

Output

Output one integer — the smallest possible time of the later vehicle's arrival in town n. If it's impossible for at least one of the vehicles to reach town n, output  - 1. 输出最短路径

Examples

input 4 2 1 3 3 4

output 2

Note In the first sample, the train can take the route 1→3→4 and the bus can take the route1→2→4 . Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town 4.

一道最简单的最短路径问题，权重可以看作 1。

题目大意是有铁路和公路两种路，而且两种方式走的交通工具不能在中途相遇。

此外，有铁路的地方肯定没有公路。

这种情况下就会有一个结论，就是至少有一种交通可以直接1到n。

这样只需要对另一种跑一个最短路就 OK 了。

#include <algorithm>
#include <queue>
#include <string.h>

// 图
int g[410][410];

//0号节点到节点i的路径长度
int d[410];

int main() {
#ifdef __MSYS__
    freopen("test.txt", "r", stdin);
#endif

    // 输入部分
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a, --b;
        g[a][b] = g[b][a] = 1;
    }

    std::queue<int> q;
    //放入0号节点
    q.push(0);
    memset(d, -1, sizeof(d));
    d[0] = 0;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        // 最后一个节点
        if (v == n - 1) {
            printf("%d\n", d[v]);
            return 0;
        }
        // 遍历所有相邻的节点
        for (int i = 0; i < n; i++)
            //g[v][i]为0，g[0][n-1]为1，如果火车直连，那么g[v][i]不能有火车，也就是0，计算的是汽车的最短路径
            //g[v][i]为1，g[0][n-1]为0，如果火车不直连，那么汽车必然是直连的，计算的是火车的最短路径
            if (g[v][i] ^ g[0][n - 1]) {
                if (d[i] == -1) {
                    q.push(i);
                    d[i] = d[v] + 1;
                }
            }
    }
    printf("-1\n");
    return 0;
}

这里使用的是Dijkstra（注意后面没有字母 l）算法，这里我们简单回顾一下 dij 算法。

首先，对于一个网络 G，我们选取一个点A作为起始点，放入队列 Q。

然后，我们开始处理队列 Q，如果 Q 存在元素，就一直执行。

每次执行，都是从队列中取得 d 值最小的元素 v，然后遍历这个 v 相邻的节点 i，如果 d[i]为 INF，也就是离节点 A 的距离为无穷大，那么就将这个元素加入到 Q 中，更新 d[i]=min{d[i], d[i]+w[v][i]}。

对于 dij 算法来说，可以将图分为 2 部分，一部分是 dij 的最短路图 G1，另外剩下的是还没有加入的图 G2。每次循环都会在 G2 中寻找节点 i，这个节点 i 必须是 G2 中 d 值最小的，然后更新节点 i 相邻的节点的 d 值。整个过程是 G2 的节点流向 G1，最终 G1 就是一个最短路径图。