AcWing 920. 最优乘车

一、邻接矩阵+BFS

#include 

using namespace std;

const int N = 510;
typedef pair PII;

int n;       //总共有N个车站
int m;       //开通了M条单程巴士线路
int g[N][N]; //邻接矩阵装图
int stop[N]; //站点数组

int bfs() {
    queue q;

    for (int i = 1; i <= n; i++)
        if (g[1][i]) { //有路，走
            q.push({i, 0});
            g[1][i] = 0; //标识已走过
        }

    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (t.first == n) return t.second; //找到

        for (int i = 1; i <= n; i++) { //枚举每个可能走的路线
            if (g[t.first][i]) {
                q.push({i, t.second + 1});
                g[t.first][i] = 0;
            }
        }
    }
    //返回无路可走
    return -1;
}

int main() {
    cin >> m >> n; // m条边，n个节点
    string line;
    getchar();                   //读掉换行
    while (m--) {                // m条边
        getline(cin, line);      //读入一行
        stringstream ssin(line); //以流的形式ssin这一行，因为每一行不知道有多少个站点,不知道什么时候结束
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p; //记录一共几个站点
        //每个汽车的前站达到后站的距离都为1 因为是同一辆车 未换车
        for (int i = 0; i < cnt; i++)
            for (int j = i + 1; j < cnt; j++)
                g[stop[i]][stop[j]] = 1; //记录两个站点间有一条公交线
    }
    //因为边权为1，所以可以使用bfs
    int res = bfs();
    if (res == -1)
        cout << "NO" << endl;
    else
        cout << res << endl;

    return 0;
}

二、链式前向星+Dijkstra

#include 

using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair PII;

const int N = 1e5 + 10, M = 2 * N;

int n; //总共有N个车站
int m; //开通了M条单程巴士线路
int h[N], e[M], w[M], ne[M], idx;
int dist[N]; //最小距离数组
int stop[N]; //站点数组
bool st[N];  //是否在队列中

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
void dijkstra() {
    memset(dist, 0x3f, sizeof dist);                  //求最小设最大
    dist[1] = 0;                                      // 1到自己，乘车数0
    priority_queue, greater> q; //小顶堆
    q.push({0, 1});                                   // 1号入队列

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second, d = t.first;
        if (!st[u]) {
            st[u] = true;
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[u] + w[i]) {
                    dist[j] = dist[u] + w[i];
                    q.push({dist[j], j});
                }
            }
        }
    }
}

int main() {
    cin >> m >> n; // m条边，n个节点
    getchar();     //读掉换行
    memset(h, -1, sizeof h); //初始化邻接表

    while (m--) {
        string s;
        getline(cin, s);
        stringstream ss(s);
        int cnt = 0;
        while (ss >> stop[cnt]) cnt++;
        for (int j = 0; j < cnt; j++)
            for (int k = j + 1; k < cnt; k++)
                add(stop[j], stop[k], 1);
    }

    dijkstra();
    if (dist[n] == INF)
        cout << "NO\n";
    else
        cout << max(0, dist[n] - 1) << '\n';
    return 0;
}