题目

https://ac.nowcoder.com/acm/contest/4862/K

类似题推荐：小雨坐地铁

思路

题目的意思是给你m条单向巴士线路和n个站点，然后从1到n最少要换乘多少次。

很容易想到使用最短路Dijkstra算法，但是难点在于如何建图。这边需要有一个分层图的思想，分离站点和巴士线路，具体见样例：

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

对应建立图则表达为：

由于需要使换乘次数最少，不妨令上车时需要1元钱，下车不要钱。图中绿色的均为巴士线路，橘色的是各个站点，箭头表示方向，上面的数字是权值，那么该图表示的便是前面的所述。

struct Node {
    int n,w;
    int operator<(const Node &o) const {
        return w > o.w;
    }
};

const int MAXN = 1000000; // 由于下面使用了i * n，那就多开一点

vector<Node> g[MAXN];
int dis[MAXN];
int vis[MAXN] = {0};

int main()
{
    int m,n;
    scanf("%d%d ",&m,&n);
    string str;
    int in;
    int f,ff = -1;
    for (int i = 1;i <= m;i ++) {
        getline(cin, str);
        stringstream ss(str);
        f = 1;
        while (ss >> in) {
            if (f) {
                f = 0;
                ff = in;
            } else {
                g[i * n + ff].push_back({i * n + in,0}); // 建立单向巴士线路，ff为上一个
                ff = in;
            }
            g[i * n + in].push_back({in,0}); // 建立巴士线路上的点到虚点（图中橘色的点）的路径，权值=0
            g[in].push_back({in + i * n,1}); // 建立虚点到巴士线路上的路径，权值=1
        }
    }
    return 0;
}

这时，我们只需跑一边最短路模版即可求出最少的权值，也就是说花最少的钱乘车。

void dij(int s) {
    mem(dis,-1);

    priority_queue<Node> q;
    q.push({s,dis[s] = 0});

    Node current;
    int k;
    while (!q.empty()) {
        current = q.top();
        q.pop();
        if (vis[current.n]) continue;
        vis[current.n] = 1;

        for (auto to : g[current.n]) {
            k = dis[current.n] + to.w;
            if (dis[to.n] == -1 || dis[to.n] > k) {
                q.push({to.n,dis[to.n] = k});
            }
        }
    }
}

求完最短路之后，我们得到的是最少的钱，由于之前设乘车需要一块钱，那么根据题意，只需记录换乘的次数即可，因此 钱-1 便是换乘的次数，若到不了，则输出NO。

if (dis[n] == -1) printf("NO\n");
else printf("%d\n",dis[n] - 1);

完整代码

//
//  header_useful.h
//  c++_acm
//
//  Created by JackLee_Void on 2019/7/23.
//  Copyright © 2019 JackLee_Void. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */

struct Node {
    int n,w;
    int operator<(const Node &o) const {
        return w > o.w;
    }
};

const int MAXN = 1000000;

vector<Node> g[MAXN];
int dis[MAXN];
int vis[MAXN] = {0};

void dij(int s) {
    mem(dis,-1);

    priority_queue<Node> q;
    q.push({s,dis[s] = 0});

    Node current;
    int k;
    while (!q.empty()) {
        current = q.top();
        q.pop();
        if (vis[current.n]) continue;
        vis[current.n] = 1;

        for (auto to : g[current.n]) {
            k = dis[current.n] + to.w;
            if (dis[to.n] == -1 || dis[to.n] > k) {
                q.push({to.n,dis[to.n] = k});
            }
        }
    }
}

int main()
{
    int m,n;
    scanf("%d%d ",&m,&n);
    string str;
    int in;
    int f,ff = -1;
    for (int i = 1;i <= m;i ++) {
        getline(cin, str);
        stringstream ss(str);
        f = 1;
        while (ss >> in) {
            if (f) {
                f = 0;
                ff = in;
            } else {
                g[i * n + ff].push_back({i * n + in,0});
                ff = in;
            }
            g[i * n + in].push_back({in,0});
            g[in].push_back({in + i * n,1});
        }
    }
    dij(1);
//    for (int i = 1;i <= n;i ++) {
//        printf("%d ",dis[i]);
//    }
//    printf("\n");
    if (dis[n] == -1) printf("NO\n");
    else printf("%d\n",dis[n] - 1);
    return 0;
}