216 . 特價航空公司

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (5/5)

Tags

ioicamp ioicamp-2021

Description

有 n 座城市編號 1,2,...,n 和一些航線及其價格，想要從城市 1 出發，經過一些城市轉機到目標城市。

航班中有 m 條是普通航班，搭乘普通航班時一定要正常付費。

航班中有 k 條是促銷航班，搭乘促銷航班時可以選擇正常付費或是免費，但是選擇免費是有條件的。

當一個人付費買票後，他會成為臨時會員狀態。如果他的緊鄰的下一趟航程是促銷航班，他可以選擇免費，反之則不可以。在搭乘一次免費航程後，會馬上變回非會員狀態。

免費航班和促銷航班都是單向的。

問目標城市是 2,3,...,n 的時候，最小花費分別為何？

Input Format

第一行是 n,m,k 分別代表城市、普通航線數量以及促銷航線數量。

之後有 m 行三個數字 u,v,w 代表普通航線的起始點、終點和費用。

之後有 k 行三個數字 u,v,w 代表促銷航線的起始點、終點和費用。

  • 1≤n≤300000
  • 0≤m,k≤300000
  • 1≤u,v≤n
  • 0≤w≤109
  • 對任意兩城市 u,v，至多只有一條從 u 到 v 的航班

Output Format

輸出一行 n−1 個整數，分別代表到第 2,3,4,...,n 個城市的最小花費。

如果無法抵達，請輸出 −1。

Sample Input 1

4 2 3
1 2 5
1 3 3
2 4 4
3 4 7
2 3 9

Sample Output 1

5 3 3

Sample Input 2

4 3 0
1 2 2
2 3 3
4 3 1

Sample Output 2

2 5 -1

Hints

每一個城市都有兩個平行世界，一個是臨時會員世界，一個是普通世界，航班事實上是在平行世界間穿梭......

Problem Source

IOICamp 2021 Day3 pI

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 1 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2
25 2000 262144 65536 2
26 2000 262144 65536 2
Submit
Back to Top