No.3616 WK vs AT vs MT vs SP
タグ : / 解いたユーザー数 26
作問者 :
kazuppa
/ テスター :
Problem Statement
Kazuppa Town has $N$ locations and $R$ roads. Road $i$ allows bidirectional travel between location $U_i$ and location $V_i$; traveling along it takes $W_i$ minutes on foot, $A_i$ minutes by automatic car, and $M_i$ minutes by manual car. There are no other means of transportation for traveling along roads.
Also, since Kazuppa Town faces the sea, it is possible to travel between locations by boat. Traveling from location $i$ to location $j$ by boat takes $S_i+S_j+C$ minutes.
In addition, licenses can be obtained at each location. At location $i$, obtaining an automatic-only license takes $X_i$ minutes, obtaining a manual license takes $Y_i$ minutes, and obtaining a boat license takes $Z_i$ minutes.
In Kazuppa Town, the available means of transportation depend on the licenses held, as follows.
- If you hold neither of the car licenses, only walking can be used for traveling along roads.
- If you hold an automatic-only license but not a manual license, only walking or an automatic car can be used for traveling along roads.
- If you hold a manual license, walking, an automatic car, or a manual car can be used for traveling along roads.
- A boat can be used only if you hold a boat license.
Bread initially is at location $1$ and holds no licenses. Find the minimum number of minutes in which he can arrive at location $N$ when acting optimally.
Constraints
- $1\leq N\leq 30000$
- $1\leq R\leq 60000$
- $1\leq C\leq 10^{14}$
- $1\leq X_i,Y_i,Z_i\leq 10^9$
- $1\leq S_i\leq 10^{14}$
- $1\leq U_i< V_i\leq N$
- $1\leq W_i,A_i,M_i\leq 10^9$
- All inputs are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask Name | Score | Constraints |
|---|---|---|
| Subtask 1 | 20 points | $N=2,\ R=1$ |
| Subtask 2 | 40 points | $W_i=A_i=M_i=1,\ C=10^{14}$, and it is possible to reach location $N$ from location $1$ by following some roads |
| Subtask 3 | 50 points | $W_i=A_i=M_i,\ C=10^{14}$, and it is possible to reach location $N$ from location $1$ by following some roads |
| Subtask 4 | 50 points | $C=10^{14}$, and it is possible to reach location $N$ from location $1$ by following some roads |
| Subtask 5 | 50 points | $W_i=A_i=M_i$ |
| Subtask 6 | 40 points | No additional constraints |
Input
$N\ R\ C$ $X_1\ X_2\ \dotsc\ X_N$ $Y_1\ Y_2\ \dotsc\ Y_N$ $Z_1\ Z_2\ \dotsc\ Z_N$ $S_1\ S_2\ \dotsc\ S_N$ $U_1\ V_1\ W_1\ A_1\ M_1$ $U_2\ V_2\ W_2\ A_2\ M_2$ $\vdots$ $U_R\ V_R\ W_R\ A_R\ M_R$
Output
Output the answer on one line.
Sample
Sample 1
Input
5 6 2 10 100 1 1000 10000 10 1 100 1000 10000 1 1 1 1 1 10000 1000 100 10 1 1 2 10 10 10 1 3 1 1 1 1 4 10 10 10 2 3 10 1 1 2 4 10 10 1 3 4 10 10 10
Output
19
Consider the following sequence of actions.
- Obtain a boat license at location $1$. This takes $1$ minute.
- Travel from location $1$ to $3$ on foot. This takes $1$ minute.
- Obtain an automatic-only license at location $3$. This takes $1$ minute.
- Travel from location $3$ to $2$ by automatic car. This takes $1$ minute.
- Obtain a manual license at location $2$. This takes $1$ minute.
- Travel from location $2$ to $4$ by manual car. This takes $1$ minute.
- Travel from location $4$ to $5$ by boat. This takes $10+2+1=13$ minutes.
In this case, the total time taken is $19$ minutes.
It is impossible to take less than $19$ minutes, so output $19$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。