問題一覧 > 通常問題

No.3616 WK vs AT vs MT vs SP

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 26
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
お気に入りにしたユーザー ProblemId : 13638 / 自分の提出
問題文最終更新日: 2026-08-06 13:49:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Paken新入生コンday1 (順位表) の他の問題:

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 120 points$N=2,\ R=1$
Subtask 240 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 350 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 450 points$C=10^{14}$, and it is possible to reach location $N$ from location $1$ by following some roads
Subtask 550 points$W_i=A_i=M_i$
Subtask 640 pointsNo 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もしくは右上の雲マークをクリックしてアカウントを作成してください。