题目描述

H城是一个旅游胜地，每年都有成千上万的人前来观光。

为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。

每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。

一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。

现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。

写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换乘的次数最少。

输入格式
第一行有两个数字M和N，表示开通了M条单程巴士线路，总共有N个车站。

从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息，其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

输出格式
共一行，如果无法乘巴士从饭店到达S公园，则输出”NO”，否则输出最少换乘次数，换乘次数为0表示不需换车即可到达。

数据范围
1≤M≤100,
1≤N≤500

样例

输入样例：
3 7
6 7
4 7 3 6
2 1 3 5

输出样例：
2

(Dijkstra算法变型)

这道题通常做法是对每条线路的N个点两两建边，然后做一次BFS，一共是$O(mn^{2})$复杂度，主要的时间都花费在了两两建边上。

所以我在想，可不可以只对每条线路上的相邻两个点建边，然后做一次类似Dijkstra算法的变型，把原来的最小cost变为最小乘车次数。

1. 我们在建图的时候，对于每一条线路，只对相邻的两个点建边，边的权值为线路的标号，这个标号的具体数值不重要，只需要让每条线路的标号不一样。

2. 同样用一个d[N]数组来记录对于每个点，到源点所需要的的最小乘车次数，初始化为INF。

3. 和原版Dijkstra算法一样，每次找出最小的d[u], 然后更新相邻的结点。更新步骤略有不同，我们需要
   判断u -> v的边的权值是不是和到u的最小乘车路线的最后一站路线权值一样，如果不一样，则乘车次数加一。这个判断是不完整的，因为到u的最小乘车线路的最后一站不一定唯一，所以我们需要用一个unordered_set来记录到u点的最小乘车线路的最后一条边的所有可能的权值。然后判断u -> v这条边是不是在那个set里面。

时间复杂度

$O(n^{2})$朴素
$O(mlogn)$堆优化

C++ 代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unordered_set>

using namespace std;

const int N = 510;
const int M = 110 * 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N], e[M], ne[M], w[M], idx;
int d[N];
unordered_set<int> pre[N]; // pre数组记录所有可能的到u的最小乘车路线的最后一站路线的标号
bool vis[N];
char tmp[4000];
int a[N];

void add_edge(int u, int v, int c) {
    e[idx] = v;
    w[idx] = c;
    ne[idx] = g[u];
    g[u] = idx++;
}

int dijkstra() {
    if (n == 1) return 0;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int v = 1; v <= n; ++v) {
            if (!vis[v] && (u == -1 || d[u] > d[v])) u = v;
        }
        vis[u] = true;
        if (u == n) break;
        for (int i = g[u]; i != -1; i = ne[i]) {
            int v = e[i];
            int diff = pre[u].find(w[i]) == pre[u].end();
            if (d[v] > d[u] + diff) {
                d[v] = d[u] + diff;
                pre[v].clear(); // 找到更小的路线，则需要清空原来的标号记录。
                pre[v].insert(w[i]);
            } else if (d[v] == d[u] + diff) {
                pre[v].insert(w[i]);
            }
        }
    }    
    return d[n] - 1;
}

int main() {
    memset(g, -1, sizeof g);
    fgets(tmp, 4000, stdin);
    char *p = strtok(tmp, " ");
    m = atoi(p);
    p = strtok(NULL, " ");
    n = atoi(p);
    while (m--) {
        fgets(tmp, 4000, stdin);
        int cnt = 0;
        char *token = strtok(tmp, " ");
        while (token != NULL) {
            int val = atoi(token);
            a[cnt++] = val;
            token = strtok(NULL, " ");
        }
        for (int i = 0; i < cnt - 1; ++i) {
            // 只对相邻点建边，权值为标号。
            add_edge(a[i], a[i + 1], m); 
        } 
    }
    int ans = dijkstra();
    if (ans < INF >> 1) printf("%d\n", ans);
    else printf("NO\n");
    return 0;
}