[POI 2020/2021 R3] Droga do domu

Luogu

IDLGP9402

Time1000ms

Memory512MB

DifficultyP5

图论2020POI（波兰）图论建模最短路

$n$ 个点，$m$ 条边，无重边自环，边有长度。 $1$ 号点是学校，$n$ 号点是家。 $s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。只计算路上时间和等车时间。换乘时间不计。 ## Input 第一行：五个整数 $n,m,s,k,t$。接下来 $m$ 行：每行三个整数 $a,b,c$，表示有一条边连接 $a,b$，长度为 $c$。接下来 $2s$ 行：每两行描述一条公交线路： - 第一行三个整数 $l,x,y$，表示它共停靠 $l$ 个点，第一班在时刻 $x$ 发车，每两班之间时间间隔为 $y$。 - 第二行 $l$ 个整数 $v_1,\dots,v_l$，依次为它停靠的 $l$ 个点。 ## Output 一行一个整数，答案。如果不能到家，那么输出一行一个字符串 `NIE`。 [samples] ## Background 译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Droga do domu](https://szkopul.edu.pl/problemset/problem/ZfS_tobZ_7xdR6D5s6Tegur3/statement/)。 d1t1。 ## Note 样例解释：![](https://cdn.luogu.com.cn/upload/image_hosting/9njsvc34.png) 对于全部数据，$2\leq n\leq 10000$，$1\leq m\leq 50000$，$1\leq s\leq 25000$，$0\leq k\leq 100$，$0\leq t\leq 10^9$，$1\leq c\leq 10^9$，$2\leq l\leq n$，$0\leq x\leq 10^9$，$1\leq y\leq 10^9$，$1\leq a,b,v\leq n$，$\sum l\leq 50000$。 | 子任务编号 | 限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $k=n$ | 20 | | 2 | $v_i<v_{i+1}$ | 20 | | 3 | $l=2$ | 20 | | 4 | $t=0,x=0,y=1$ | 20 | | 5 | | 20 |

Samples

Input #1

Output #1

Input #2

10 45 17 10 123
1 2 1
1 3 100
1 4 100
1 5 100
1 6 100
1 7 100
1 8 100
1 9 100
1 10 100
2 3 1
2 4 100
2 5 100
2 6 100
2 7 100
2 8 100
2 9 100
2 10 100
3 4 1
3 5 100
3 6 100
3 7 100
3 8 100
3 9 100
3 10 100
4 5 1
4 6 100
4 7 100
4 8 100
4 9 100
4 10 100
5 6 1
5 7 100
5 8 100
5 9 100
5 10 100
6 7 1
6 8 100
6 9 100
6 10 100
7 8 1
7 9 100
7 10 100
8 9 1
8 10 100
9 10 1
2 0 1
1 2
2 0 1
1 3
2 0 1
2 3
2 0 1
2 4
2 0 1
3 4
2 0 1
3 5
2 0 1
4 5
2 0 1
4 6
2 0 1
5 6
2 0 1
5 7
2 0 1
6 7
2 0 1
6 8
2 0 1
7 8
2 0 1
7 9
2 0 1
8 9
2 0 1
8 10
2 0 1
9 10

Output #2

Input #3

见附件

Output #3

1000000102

Input #4

见附件

Output #4

11100000071

API Response (JSON)

{
  "problem": {
    "name": "[POI 2020/2021 R3] Droga do domu",
    "description": {
      "content": "$n$ 个点，$m$ 条边，无重边自环，边有长度。 $1$ 号点是学校，$n$ 号点是家。 $s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。 在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。 只计算路上时间和等车时间。换乘时间不计。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9402"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$n$ 个点，$m$ 条边，无重边自环，边有长度。\n\n$1$ 号点是学校，$n$ 号点是家。\n\n$s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。\n\n在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。\n\n只计算路上时间和等车时间。换乘时间不计。\n\n## Input\n\n第一行：五个整数 $n,m,s,k,t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments