#P2021045. 疫苗运输

    ID: 140 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>入门赛制:OI来源:wyfoj http://127.0.0.1最短路

疫苗运输

疫苗运输

题目描述

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

X 市的物流系统并不发达,只有n个物流站点(以下简称“站点”)和m条物流线路(以下简称“线路”),且该物流系统具有以下几个特点:

每条线路都是环线。即,从某个站点出发,经过一系列不重复的站点,最终回到出发站点。

每条线路上有且仅有一辆运输车,以固定的时刻表(相邻站间的时间间隔)在环线上不断运行。在 0 时刻时,运输车在出发站点。

运输车上配备了容量足够大的制冷系统,疫苗可以在车上长时间存放。但是换乘(从一条线路切换到另一条线路)必须在同一个站点同一个时刻发生——因为各个站点没有独立的制冷系统,疫苗不能在站点内下车等待。

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

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

输入格式

第一行两个整数n,m。

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

输出格式

输出n−1行,第i行表示将疫苗送达第i+1个站点的最早时间:

如果能在有限时间内送达,输出最早的送达时刻;否则输出inf。

数据范围

(原站未提供,导入后需人工补齐)

样例

5 2
3 1 100 2 100 3 100
3 3 100 4 100 5 100
100
200
inf
inf
5 3
3 1 100 2 100 3 100
3 3 100 4 100 5 100
2 3 125 5 125
100
200
1600
625
10 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
99
26
78
245
7753
81
146
206
163

提示

样例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 号站点

评测用例规模与约定

对于 10% 的数据,n≤5,m=1,T≤10。

对于 30% 的数据,n≤5,m≤2,T≤10。

对于 50% 的数据,n≤5,m≤5,T≤10。

对于 70% 的数据,n≤10,m≤10,T≤100。

对于 80% 的数据,n≤30,m≤30,T≤1000。

对于 95% 的数据,n≤100,m≤100,T≤10^5。

对于 100% 的数据,n≤500,m≤500,T≤10^6。