No.3561 Collect KCPC
タグ : / 解いたユーザー数 24
作問者 :
HoyHoyCharhang
/ テスター :
みうね
fluorine
TKTYI
jastaway
soryuusi0219
yaaya
butsurizuki
wasab1
tatesoto
KumaTachiRen
問題文
$1$ から $N$ までの番号が付いた $N$ 個の地点と $M$ 個の道があります。
$i\;(1\leq i\leq M)$ 番目の道を使うと地点 $U_i$ から地点 $V_i$ まで $C_i$ 分で移動できます。この道を逆方向に移動することはできません。
また、英大文字からなる長さ $N$ の文字列 $S = S_1S_2\cdots S_N$ が与えられます。地点 $i\;(1\leq i\leq N)$ には $S_i$ と書かれたクッキーが $1$ つおいてあります。
いま、あなたは空文字列 $T$ を持ち、地点 $1$ から出発して以下のいずれかの行動を選択して行うことを $0$ 回以上繰り返すことができます。
- 現在いる地点にクッキーがあれば食べる。$T$ の末尾にクッキーに書かれていた文字を追加する
- 現在いる地点から出ている道を使って他の地点に移動する
$T=$ KCPC とできるか判定し、できるならば道を使った時間の合計の最小値を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $U_1$ $V_1$ $C_1$ $U_2$ $V_2$ $C_2$ $\vdots$ $U_M$ $V_M$ $C_M$ $S$
- $4\leq N\leq 10^5$
- $1\leq M\leq 1.5\times 10^5$
- $1\leq U_i, V_i\leq N\;\;(1\leq i\leq M)$
- $U_i\neq V_i\;\;(1\leq i\leq M)$
- $(U_i,V_i)$ は相異なる
- $1\leq C_i\leq 10^9\;\;(1\leq i\leq M)$
- $N,M,U_i,V_i,C_i$ は整数
- $S$ は英大文字からなる長さ $N$ の文字列
部分点
この問題にはサブタスクによる部分点が設定されています。
| サブタスク名 | 配点 | 制約 |
|---|---|---|
| 部分点1 | 10 点 | $N\leq 50$ |
| 部分点2 | 20 点 | $S_i =$ C なる $i\;\;(1\leq i\leq N)$ の個数は $5$ 個以下 |
| 部分点3 | 20 点 | $U_i<V_i\;\;(1\leq i\leq M)$ |
| 部分点4 | 50 点 | 追加の制約はない |
出力
$T=$KCPC とできるならば道を使った時間の合計の最小値を $1$ 行に出力せよ。
そうでないならば -1 を出力せよ。
最後に改行せよ。
サンプル
サンプル1
入力
4 5 1 2 2 2 3 2 3 1 3 2 4 1 4 2 1 PKCC
出力
10
以下のように行動することで合計 10 分で目標を達成することができます。
- 地点 $1$ から出発する
- 地点 $1$ から地点 $2$ へ移動する ($2$ 分)
- 地点 $2$ にあるクッキーを食べる。$T=$
Kとなる - 地点 $2$ から地点 $3$ へ移動する ($2$ 分)
- 地点 $3$ にあるクッキーを食べる。$T=$
KCとなる - 地点 $3$ から地点 $1$ へ移動する ($3$ 分)
- 地点 $1$ にあるクッキーを食べる。$T=$
KCPとなる - 地点 $1$ から地点 $2$ へ移動する ($2$ 分)
- 地点 $2$ から地点 $4$ へ移動する ($1$ 分)
- 地点 $4$ にあるクッキーを食べる。$T=$
KCPCとなる
このサンプルは部分点 $1,2,4$ の制約を満たします。
サンプル2
入力
6 7 1 2 3 2 3 4 3 1 3 3 4 2 4 5 1 5 6 4 6 4 3 CPAKBC
出力
-1
どのように行動しても $T=$KCPC とすることはできません。
このサンプルは部分点 $1,2,4$ の制約を満たします。
サンプル3
入力
7 8 1 2 4 1 3 3 2 4 2 3 5 5 3 6 2 4 5 1 5 7 4 6 7 2 KKCCPCC
出力
11
このサンプルは部分点 $1,2,3,4$ の制約を満たします。
サンプル4
入力
15 20 6 15 59680731 4 14 512184729 4 7 928045980 15 12 936533142 5 2 641980757 9 3 154750438 11 6 57032185 15 2 194588886 13 14 631990846 12 5 6215057 2 12 791775040 2 9 476629800 14 5 126298100 10 11 267993404 10 1 73997749 12 8 450877870 1 13 296054234 12 10 182601287 3 4 604956581 1 14 933531002 CCCJCCCCZCCCPCK
出力
5176583842
このサンプルは部分点 $1,4$ の制約を満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。