問題一覧 > 通常問題

No.2477 Drifting

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : だれ / テスター : akakimidori りあん tsutaj beet 👑 tute7627 SPD_9X2 nok0 👑 rin204 momoyuu KKT89
お気に入りにしたユーザー ProblemId : 9863 / 自分の提出
問題文最終更新日: 2025-10-14 00:37:06
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
Japan Alumni Group Summer Camp 2023 Day 2 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。