疫苗运输

GitHub跳转原题关系图 Canvas 关系图返回列表

将线路视为可持续乘坐的状态，用 CRT 求会面时刻并做时间依赖 Dijkstra。

OJ: shumeng

题目 ID: CSP202104E

难度:省选/NOI-

标签:最短路Dijkstra中国剩余定理同余

日期: 2026-07-31 16:21

形式化题目

有 $n$ 个站点和 $m$ 条环线线路，每条线路上有一辆按固定时刻表循环运行的运输车，疫苗可长时间留在车上。换乘必须在同一站点同一时刻发生，只有 1 号站点配冷库，可以在站点等待。对 $2\sim n$ 号每个站点，求从 1 号站出发最早送达疫苗的时刻，不可达输出 inf。

思路

不能在站点等待意味着普通“到站后等下一班车”的最短路模型不适用。把状态设为“已经登上某条线路”，在线的运行过程中完成转移。

留在车上的到站时刻

若当前时刻为 $t$ ，疫苗可以一直待在车上，到达该线路任意停靠站的下一次到站时刻可以直接由该站的周期内偏移算出。

换乘的最早会面时刻

两条线路在共同站点的换乘时刻满足同余方程组

x\equiv o_i\pmod{P_i},\qquad x\equiv o_j\pmod{P_j},

其中 $P$ 是环线周期， $o$ 是该站本周期内的到达偏移。用扩展欧几里得求解：若偏移差不能被 $\gcd(P_i,P_j)$ 整除则不能换乘，否则得到不小于当前时刻 $t$ 的最早会面时刻。下一次会面随 $t$ 单调不减，满足 Dijkstra 的 FIFO 条件。

最短路

在“线路”状态图上运行 Dijkstra。初始可在 1 号冷库站等待任意经过该站的线路；最终对每个站点取所有经过它的已达线路的下一次到站时间最小值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const __int128 INF = ((__int128)1 << 120);

// 一个停靠点信息：所属线路、站点编号、本周期内的到达偏移
struct Stop {
    int line, station;
    long long offset;
};

// 一条环线：运行周期和它停靠的所有站点
struct Line {
    long long period;
    vector<Stop> stop;
};

// 最短路状态：登上某条线路的时刻
struct RouteState {
    __int128 time;
    int line;
    bool operator<(const RouteState &other) const {
        return time > other.time;
    }
};

int n, m;
Line route[MAXN];
vector<Stop> at_station[MAXN];   // 每个站点有哪些线路经过
long long gcd_value[MAXN][MAXN], lcm_value[MAXN][MAXN], inverse_value[MAXN][MAXN];
__int128 dist[MAXN];             // dist[i] 为最早登上线路 i 的时刻

// 扩展欧几里得：解 a*x + b*y = gcd(a,b)
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
    return g;
}

// 求 a 在模 mod 下的乘法逆元
long long get_inverse(long long a, long long mod) {
    if (mod == 1) return 0;
    long long x, y;
    extended_gcd(a, mod, x, y);
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

// 线路在偏移 offset 的站点，从时刻 now 之后的下一次到站时刻
__int128 next_arrival(__int128 now, long long offset, long long period) {
    __int128 remainder = now % period;
    if (remainder <= offset) return now + offset - remainder;
    return now + period + offset - remainder;
}

// 线路 first 偏移 first_offset 与线路 second 偏移 second_offset 从时刻 now 起的最早会面时刻
__int128 next_meeting(int first, long long first_offset, int second, long long second_offset, __int128 now) {
    // 解同余组：x ≡ first_offset (mod P_first)，x ≡ second_offset (mod P_second)
    long long g = gcd_value[first][second];
    long long difference = second_offset - first_offset;
    if (difference % g != 0) return INF;   // 无解，两条线在该站永远碰不上
    long long mod = route[second].period / g;
    long long k = 0;
    if (mod != 1) {
        long long value = difference / g;
        value %= mod;
        if (value < 0) value += mod;
        k = (long long)((__int128)value * inverse_value[first][second] % mod);
    }
    __int128 base = first_offset + (__int128)route[first].period * k;
    long long period = lcm_value[first][second];
    // 调整到不小于 now 的时刻
    if (base < now) base += (now - base + period - 1) / period * period;
    return base;
}

// 输出 __int128 时间
void print_time(__int128 value) {
    if (value == INF) {
        cout << "inf\n";
        return;
    }
    string text;
    do {
        text.push_back('0' + value % 10);
        value /= 10;
    } while (value);
    reverse(text.begin(), text.end());
    cout << text << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int length;
        cin >> length;
        vector<int> station(length);
        vector<long long> travel(length);
        for (int j = 0; j < length; j++) cin >> station[j] >> travel[j];
        long long offset = 0;
        for (int j = 0; j < length; j++) {
            route[i].stop.push_back({i, station[j], offset});
            at_station[station[j]].push_back({i, station[j], offset});
            offset += travel[j];
        }
        route[i].period = offset;   // 周期 = 各段行驶时间之和
    }
    // 预处理任意两条线路的 gcd、lcm 与逆元，供换乘同余求解使用
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            long long g = gcd(route[i].period, route[j].period);
            gcd_value[i][j] = g;
            lcm_value[i][j] = route[i].period / g * route[j].period;
            inverse_value[i][j] = get_inverse(route[i].period / g, route[j].period / g);
        }
    }

    // 初始：在 1 号冷库站等待任意经过它的线路
    priority_queue<RouteState> q;
    for (int i = 1; i <= m; i++) dist[i] = INF;
    for (int i = 0; i < (int)at_station[1].size(); i++) {
        Stop start = at_station[1][i];
        if (start.offset < dist[start.line]) {
            dist[start.line] = start.offset;
            q.push({start.offset, start.line});
        }
    }
    // 在"线路"状态图上跑 Dijkstra
    while (!q.empty()) {
        RouteState current = q.top();
        q.pop();
        if (current.time != dist[current.line]) continue;   // 已过期的状态
        for (int i = 0; i < (int)route[current.line].stop.size(); i++) {
            Stop here = route[current.line].stop[i];
            // 在共同站点枚举所有可能换乘的线路
            for (int j = 0; j < (int)at_station[here.station].size(); j++) {
                Stop target = at_station[here.station][j];
                if (target.line == current.line) continue;
                __int128 meeting = next_meeting(current.line, here.offset, target.line, target.offset, current.time);
                if (meeting < dist[target.line]) {
                    dist[target.line] = meeting;
                    q.push({meeting, target.line});
                }
            }
        }
    }

    // 对每个站点，取所有经过它的可达线路的下一次到站时刻
    for (int station = 2; station <= n; station++) {
        __int128 answer = INF;
        for (int i = 0; i < (int)at_station[station].size(); i++) {
            Stop target = at_station[station][i];
            if (dist[target.line] == INF) continue;
            answer = min(answer, next_arrival(dist[target.line], target.offset, route[target.line].period));
        }
        print_time(answer);
    }

    return 0;
}

复杂度

设站点在线路上的总出现次数为 $S$ 。Dijkstra 中枚举共同站点的换乘，最坏时间复杂度为 $O(S\cdot m\log m)$ ，空间复杂度为 $O(S+m^2)$ 。本题 $n,m\le 500$ ；会面时刻使用 __int128 防止多个周期累加溢出。

总结

不能在站点等待意味着普通“到站后等下一班车”的最短路不适用。把状态放在运行中的线路上，并把换乘限制精确写成同余方程，就能得到满足冷链条件的最早到达时间。

图示解析

text

1
2
3
4
5已登上线路 i，时刻 t
|- 留在车上 -> 线路 i 的下一次到站
`- 共同站点 s
   `- 解 i、j 在 s 的两个时间同余式
      `- 最早会面时刻 -> 登上线路 j

初始冷库是唯一可在站点等待的地方，因此它直接给每条经过 1 号站的线路一个首次可登车时间。

由于官方数据较弱，1 秒时限不够合理，本评测时限改为 2 秒。但是我们的 std 之一可以保证在 1 秒内同时通过官方数据和民间数据。
此外，新添加的 sub7-22 数据较为刁钻，如果你的实现能够通过除该点以外的全部测试点，则说明你实现了本题的一般解法（可以视为大致掌握了本题）。欢迎大家挑战并实现能够通过 sub7-22 数据的做法。

时间限制： ~~1.0 秒~~ 2.0 秒

空间限制： 512 MB

题目描述

X 市最近生产了一批疫苗，需要运往各地使用。疫苗的运输是一个困难的问题：既要实现尽快时间送达，又要保证全程冷链，否则疫苗会损坏。

X 市的物流系统并不发达，只有 $n$ 个物流站点（以下简称“站点”）和 $m$ 条物流线路（以下简称“线路”），且该物流系统具有以下几个特点：

每条线路都是环线。即，从某个站点出发，经过一系列不重复的站点，最终回到出发站点。
每条线路上有且仅有一辆运输车，以固定的时刻表（相邻站间的时间间隔）在环线上不断运行。在 $0$ 时刻时，运输车在出发站点。
运输车上配备了容量足够大的制冷系统，疫苗可以在车上长时间存放。但是换乘（从一条线路切换到另一条线路）必须在同一个站点同一个时刻发生——因为各个站点没有独立的制冷系统，疫苗不能在站点内下车等待。

现在 X 市想要从 $1$ 号站点开始，经过若干条线路的运输和换乘，将疫苗运输到各个其他站点。与其他站点不同， $1$ 号站点配有冷库。也就是说，从 $0$ 时刻开始，可以在 $1$ 号站点等待某条线路运输车的到来，再开始疫苗运输。问对于 $2$ 号 $\sim n$ 号站点，分别最早可以在什么时刻将疫苗送到该站点。

注意：每个问题是独立的，即只需要求出 $1$ 号站点到各个站点的最早送达时刻。

输入格式

从标准输入读入数据。

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行表示一条物流线路。对于第 $i\ (1 \leq i \leq m)$ 条线路，首先有一个整数 $l_i\ (2 \leq l_i \leq n)$ 表示该线路经过的站点个数。接下来 $2 l_i$ 个整数，第 $2j-1$ 和第 $2j$ 个整数分别表示该线路的第 $j\ (1 \leq j \leq l_i)$ 个站点的编号 $a_{i,j}\ (1 \leq a_{i,j} \leq n)$ ，以及该线路的第 $j$ 个站点到下一个站点所需的时间 $t_{i,j}\ (1 \leq t_{i,j} \leq T)$ （对于第 $l_i$ 个站点即为它到第 1 个站点的时间）。其中，每条线路的第 $1$ 个站点为其出发站点。输入中同一行相邻的整数，均用一个空格隔开。

输出格式

输出到标准输出。

输出 $n - 1$ 行，第 $i$ 行表示将疫苗送达第 $i+1$ 个站点的最早时间：如果能在有限时间内送达，输出最早的送达时刻；否则输出 inf。

input1

1
2
35 2
3 1 100 2 100 3 100
3 3 100 4 100 5 100

output1

1
2
3
4100
200
inf
inf

input2

1
2
3
45 3
3 1 100 2 100 3 100
3 3 100 4 100 5 100
2 3 125 5 125

output2

样例 2 解释

在此样例中，有 5 个站点、3 条线路。第一条线路经过站点 1、2、3，第二条线路经过站点 3、4、5，第三条线路经过站点 3 和 5。

以下为从 1 号站点到各个其他站点的最早送达路线：

2 号站点：通过第一条线路运输，在 100 时刻到达 2 号站点
3 号站点：通过第一条线路运输，在 200 时刻到达 3 号站点
4 号站点：通过第一条线路运输，在 500 时刻到达 3 号站点，然后换乘第三条线路，在 1500 时刻再次到达 3 号站点，最后换乘第二条线路，在 1600 时刻到达 4 号站点
5 号站点：通过第一条线路运输，在 500 时刻到达 3 号站点，然后换乘第三条线路，在 625 时刻到达 5 号站点

input3

1
2
3
4
5
610 5
6 8 18 1 8 3 52 4 3 7 18 2 47
6 8 96 2 45 10 44 6 95 4 97 3 96
4 10 63 8 97 7 75 1 12
7 3 7 5 75 1 19 2 37 4 25 10 43 9 32
2 6 35 5 74

output3

子任务

对于所有数据，保证 $n,m\le 500,T\le 10^6$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$m\le$	$T\le$
1	10	$5$	$1$	$10$
2	20	$5$	$2$	$10$
3	20	$5$	$5$	$10$
4	20	$10$	$10$	$100$
5	10	$30$	$30$	$1000$
6	15	$100$	$100$	$10^5$
7	5	$500$	$500$	$10^6$

疫苗运输

目录

形式化题目

思路

留在车上的到站时刻

换乘的最早会面时刻

最短路

代码

复杂度

总结

图示解析