思路与算法

为每个站台和每条线路中的每个出现位置分别建点。位置i的公交在时刻t≡i(mod线路长)出现，站台到该位置的边需等到下一次该相位；位置到本站台0时间，位置到线路下一个位置1时间。对这些FIFO时变边跑Dijkstra，读出各站台最早时刻。

正确性说明

每个合法登车动作等价站台边的最小非负等待，继续坐车和下车分别对应两种位置边，因而实际旅途与状态路径互相对应。提前到站可以等到任何更晚登车时刻，所以到达时间不会因更早出发变差，FIFO保证最小标签定型正确。

复杂度

设L=Σti≤200000，图有N+L个点、O(L)隐式边。读入与初始化O(N+L)，堆Dijkstra O((N+L)log(N+L))，空间O(N+L)。

易错点

同一站台可在一条线路出现多次，各相位必须分开。下车不耗时，坐到下一站耗1；最后一位置循环到线路首位。不可达输出-1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> at, phase, period, nxt;
    vector<vector<int>> occ(n);
    for (int j = 0; j < m; j++) {
        int k;
        cin >> k;
        int base = at.size();
        for (int i = 0; i < k; i++) {
            int s;
            cin >> s;
            --s;
            at.push_back(s);
            phase.push_back(i);
            period.push_back(k);
            nxt.push_back(base + (i + 1) % k);
            occ[s].push_back(base + i);
        }
    }
    int L = at.size();
    const long long INF = 1LL << 60;
    vector<long long> d(n + L, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    auto relax = [&](int v, long long x) {
        if (x < d[v]) {
            d[v] = x;
            q.push({x, v});
        }
    };
    relax(0, 0);
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        long long tm = t.first;
        int u = t.second;
        if (d[u] != tm)
            continue;
        if (u < n) {
            for (int i : occ[u])
                relax(n + i, tm + (phase[i] - tm % period[i] + period[i]) % period[i]);
        } else {
            int i = u - n;
            relax(at[i], tm);
            relax(n + nxt[i], tm + 1);
        }
    }
    for (int i = 1; i < n; i++)
        cout << (d[i] == INF ? -1 : d[i]) << (i + 1 == n ? '\n' : ' ');
    if (n == 1)
        cout << '\n';
}