题目描述

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

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

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

输入格式

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

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

样例

输入

3 7
6 7
4 7 3 6
2 1 3 5

输出

2

算法

(堆优化Dijkstra)

思路：一条线上的点，那么任意一个点到其他点的距离都是1，因为是一条线路。
用优先队列每次找到堆顶的最小的距离以及点号，再用这个点去更新其他点的距离。
最后dist[n] - 1就是换承的次数。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int dist[N], e[N], ne[N], head[N], idx, n, m, weight[N];
typedef pair<int, int> PII;
bool isSured[N];
priority_queue<PII, vector<PII> , greater<PII> > q;

void add(int a, int b){
    e[idx] = b, ne[idx] = head[a], weight[idx] = 1, head[a] = idx++;
}

int Dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII> , greater<PII> > heap;
    heap.push({dist[1], 1});
    while(!heap.empty()){
        auto t = heap.top();
        heap.pop();
        int pdist = t.first, pid = t.second;
        if(isSured[pid])    continue;
        isSured[pid] = true;
        for(int i = head[pid]; i != -1; i = ne[i]){
            if(dist[e[i]] > pdist + weight[i]){
                dist[e[i]] = pdist + weight[i];
                heap.push({dist[e[i]], e[i]});
            }
        }
    }
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main(){
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof head);
    cin >> m >> n;
    for(int i = 0; i < m; i++){
        int x;
        vector<int> t;
        while(cin >> x){
            t.push_back(x);
            if(cin.get() == '\n')   break;
        }
        for(int j = 0; j < t.size() - 1; j++){
            for(int k = j + 1; k < t.size(); k++)   add(t[j], t[k]);
        }
    }
    int ans = Dijkstra();
    if(ans == -1)   cout << "NO";
    else    cout << ans - 1;
    return 0;
}

算法2

(floyd) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla