14 . 跳島旅行
TopCoder
Tags
Description
Fysty 今天來到了埃歐埃國，埃歐埃國總共有 $n$ 座島嶼，編號分別是 $1$ 到 $n$，其中最著名的兩個島：埃歐島與埃西島的編號分別是 $s$ 和 $t$，這兩個島也是唯二有旅店可以住宿的島嶼。 Fysty 想藉由安排一次跳島旅行來探索偌大的埃歐埃國，這趟旅行會持續 $q$ 天，每天 Fysty 都會從前一天住宿的島嶼前往 $a_j$ 島遊玩，再到另一個島嶼過夜，請注意 Fysty 不喜歡連續兩天住在同一個島嶼，所以他會輪流在埃歐島和埃西島過夜。第一天的時候他會從埃歐島出發。在埃歐埃國上總共有 $m$ 條航線，第 $i$ 條航線在任一時刻都會有一艘小艇從第 $u_i$ 個島嶼出發前往第 $v_i$ 個島嶼，同時也有另一艘小艇從第 $v_i$ 個島嶼出發前往第 $u_i$ 個島嶼，票價皆為 $c_i$ 元。請你幫 Fysty 算出他每天共需要花費至少多少錢在買船票上，並且在花費最少錢的前提下，他安排航線的選擇數對 $10^ 9+7$ 取模的餘數。
Input Format
輸入的第一行包含五個整數 $n, m, q, s, t$，分別代表埃歐埃國的島嶼數目、航線數目、Fysty 想要遊玩的天數、埃歐島的編號及埃西島的編號。
第二行包含 $q$ 個介於 $1$ 到 $n$ 的整數 $a_j$，代表 Fysty 第 $j$ 天時想去遊玩的島嶼的編號。($1\leq j\leq q$)
接下來的 $m$ 行，每行包含三個整數 $u_i, v_i, c_i$，代表第 $i$ 個航線有票價為 $c_i$ 往返 $u_i$ 島與 $v_i$ 島的航班。($1\leq i\leq m$)
- $2\leq n\leq 10^ 5$
- $n-1\leq m\leq min(\frac{n\cdot(n-1)}{2}, 2\cdot 10^ 5)$
- $1\leq q\leq 10^ 5$
- $1\leq s, t\leq n$, $s\neq t$
- $1\leq a_j\leq n$
- $1\leq u_i < v_i\leq n$，且 $\forall x\neq y, (u_x, v_x)\neq(u_y, v_y)$
- $1\leq c_i\leq 10^ 9$
- 保證兩個島嶼之間一定可以藉由小艇互相到達。
Output Format
輸出 $q$ 行，每行包含兩個整數，分別代表該天買船票的最小花費以及安排航線的可能選擇數對 $10^ 9+7$ 的餘數。
Sample Input 1
6 5 6 2 4
1 2 3 4 5 6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 2 3 4 5 6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
Sample Output 1
4 1
2 1
2 1
2 1
4 1
6 1
2 1
2 1
2 1
4 1
6 1
Sample Input 2
7 9 7 4 7
1 2 3 4 5 6 7
1 2 2
2 3 5
3 4 4
4 5 10
5 6 3
1 6 7
1 7 3
4 7 5
3 6 1
1 2 3 4 5 6 7
1 2 2
2 3 5
3 4 4
4 5 10
5 6 3
1 6 7
1 7 3
4 7 5
3 6 1
Sample Output 2
11 1
14 1
13 1
5 1
21 2
15 2
5 1
14 1
13 1
5 1
21 2
15 2
5 1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~33 | 無特別限制 | 100 |