No.2477 Drifting
Problem Statement
You are given a weighted directed graph with $N$ vertices and $M$ edges, where the vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $M$. The $i\ (1\leq i \leq M)$-th edge goes from vertex $u_i$ to vertex $v_i$ $(u_i \lt v_i)$, and its weight is $w_i$.
You are also given $K$ triples of integers. The $i\ (1\leq i \leq K)$-th triple is $(a_i,b_i,c_i)\ (a_i < b_i < c_i)$.
You are initially at vertex $1$, and you want to reach vertex $N$ by repeatedly moving to a vertex along an edge.
However, for every $i\ (1\leq i \leq K)$, if you move from vertex $a_i$ to vertex $b_i$, your next move must be to a vertex other than vertex $c_i$.
Determine whether you can reach vertex $N$. If you can, also find the minimum possible total weight of the edges you traverse.
Constraints
- All input values are integers.
- $3\leq N\leq 2\times 10^5$
- $0\leq M\leq 2\times 10^5$
- $1\leq u_i\lt v_i \leq N$ $(1\leq i\leq M)$
- $i\neq j \Rightarrow (u_i, v_i)\neq (u_j, v_j)$ $(1\leq i, j\leq M)$
- $1\leq w_i\leq 10^9$ $(1\leq i\leq M)$
- $0\leq K\leq 2\times 10^5$
- $1\leq a_i\lt b_i\lt c_i\leq N$ $(1\leq i\leq K)$
Input
$N$ $M$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\vdots$ $u_M$ $v_M$ $w_M$ $K$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $\vdots$ $a_K$ $b_K$ $c_K$
Output
If you cannot reach vertex $N$, print -1. Otherwise, print the minimum possible total weight of the edges you traverse.
Sample
Sample 1
Input
4 4 1 2 1 1 3 2 2 4 2 3 4 2 1 1 2 4
Output
4
It is optimal to move as $1 \to 3\to 4$.
Sample 2
Input
7 8 1 2 5 1 3 2 2 4 1 3 4 1 4 5 6 4 6 2 5 7 1 6 7 1 2 2 4 5 3 4 6
Output
9
It is optimal to move as $1\to 2\to 4\to 6\to 7$.
Sample 3
Input
3 2 1 2 1 2 3 1 1 1 2 3
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
だれ
akakimidori
りあん
tsutaj
beet
tute7627
SPD_9X2
nok0
momoyuu