No.3393 Move on Highway
タグ : / 解いたユーザー数 54
作問者 :
yu23578
/ テスター :
GaLLium
yt142857
aa36
Germanium32
Problem Statement
The Kingdom of yu23578 has $N$ towns numbered from $1$ to $N$ and $M$ highways numbered from $1$ to $M$. Highway $i$ bidirectionally connects town $u_i$ and town $v_i$, and its cost is $w_i$.
yu23578-kun has decided to travel by car on the highways from town $1$ to town $N$. Using the highways incurs the following charges.
- Each time highway $i$ is used, a gasoline fee of $w_i$ yen is charged.
- On arrival at town $N$, a highway toll of (total number of times roads were used) $\times C$ yen is charged.
Solve the following problem for each of $i = 2,3,\cdots,N$.
- When you visit town $i$, you obtain $1$ coupon, only on the first visit. After that, when using a highway, you can consume $1$ coupon to waive the gasoline fee once. However, the highway toll is still charged. You do not have to visit town $i$.
Under these conditions, find the minimum total charge for traveling from town $1$ to town $N$.
Constraints
- $2 \le N \le 2 \times 10^5$
- $N-1 \le M \le \mathrm{min}(\frac{N(N-1)}{2},2 \times 10^5)$
- $1 \le C \le 10^9$
- $1 \le u_i < v_i \le N$
- If $i \neq j$, then $(u_i,v_i) \neq (u_j,v_j)$
- $1 \le w_i \le 10^9$
- Every town can be reached from town $1$ via some roads.
- All inputs are integers.
Input
$N\ M\ C$ $u_1\ v_1\ w_1$ $u_2\ v_2\ w_2$ $\vdots$ $u_M\ v_M\ w_M$
Output
Output $N-1$ lines. On the $x$-th line, output the answer for $i=x+1$.
Print a newline at the end.
Sample
Sample 1
Input
3 3 1 1 2 1 1 3 3 2 3 4
Output
3 4
An example of a trip for $i = 2$ is shown below.
Move from town $1$ to town $2$. The current total gasoline fee is $1$ yen, and you hold $1$ ticket.
Move from town $2$ to town $3$. By using the ticket, the current total gasoline fee is kept to $1 + 0 = 0$ yen.
The number of roads used is $2$, so a highway toll of $1 \times 2 = 2$ yen is charged. The final charge is $1+2=3$ yen.
An example of a trip for $i = 3$ is as follows.
Move from town $1$ to town $3$. The current total gasoline fee is $3$ yen, and you hold $1$ ticket.
The number of roads used is $1$, so a highway toll of $1 \times 1 = 1$ yen is charged. The final charge is $3+1=4$ yen.
As in this trip, you may arrive at town $N$ without using the ticket.
Sample 2
Input
5 5 1000000000 1 2 1 2 3 1 3 4 1 4 5 1 1 5 1
Output
1000000001 1000000001 1000000001 1000000001
For any $i$, it is clearly optimal to go directly from town $1$ to town $5$.
Sample 3
Input
7 9 338371223 1 2 284635923 2 3 183265394 6 7 119364529 5 7 998244353 5 6 763194723 2 5 563252789 2 4 345438454 4 5 683742211 3 5 332485634
Output
1863002381 2153871843 2667301480 1863002381 2861246734 2861246734
The output may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。