NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
216 . 特價航空公司
TopCoder
Tags
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\le n\le 300000$
- $0\le m,k\le 300000$
- $1\le u,v\le n$
- $0\le w\le 10^ 9$
- 對任意兩城市 $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
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
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 |