AT_abc485_e.Colorful Route

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN cities and MM one-way roads. The ii-th road leads from city UiU_i to city ViV_i and is painted in color CiC_i.

You want to travel from city 11 to city NN by repeatedly traversing roads. However, you must not traverse roads painted in the same color twice in a row.

Determine whether it is possible to reach city NN from city 11, and if it is possible, find the minimum possible number of times you traverse a road.

有 NN 座城市和 MM 条单向道路。第 ii 条道路从城市 UiU_i 指向城市 ViV_i,且被涂成颜色 CiC_i。

你想从城市 11 出发,通过反复经过道路到达城市 NN。但你不能连续两次经过颜色相同的道路。

判断是否可能从城市 11 到达城市 NN;若可能,求出经过道路的最少次数。

输入格式

The input is given from Standard Input in the following format:

NN MM
U1U_1 V1V_1 C1C_1
U2U_2 V2V_2 C2C_2
⋮\vdots
UMU_M VMV_M CMC_M

输入从标准输入中按以下格式给出:

NN MM
U1U_1 V1V_1 C1C_1
U2U_2 V2V_2 C2C_2
⋮\vdots
UMU_M VMV_M CMC_M

输出格式

If it is impossible to reach city NN from city 11, print -1. Otherwise, print the minimum possible number of times you traverse a road.

如果无法从城市 11 到达城市 NN,则输出 -1。否则,输出你经过道路的最少次数。

输入输出样例

  • 输入#1

    6 10
    1 2 1
    2 4 2
    2 5 2
    3 6 5
    4 3 3
    5 2 3
    5 3 2
    5 6 2
    6 1 3
    6 5 3

    输出#1

    4
  • 输入#2

    3 5
    1 2 1
    1 2 1
    1 2 2
    1 2 2
    1 2 3

    输出#2

    -1
  • 输入#3

    8 10
    1 2 1
    2 3 2
    2 4 1
    3 2 3
    4 5 2
    4 6 1
    5 4 3
    6 7 2
    6 8 1
    7 6 3

    输出#3

    10

说明/提示

Sample 1 Explanation:
Let road ii denote the ii-th road. You can reach city 66 by traversing roads 1,2,5,41, 2, 5, 4 in this order.

Constraints

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ui,Vi≤N1 \leq U_i, V_i \leq N
  • Ui≠ViU_i \neq V_i
  • 1≤Ci≤M1 \leq C_i \leq M
  • All input values are integers.

样例 1 解释:
设第 ii 条道路记为道路 ii。你可以按顺序经过道路 1,2,5,41, 2, 5, 4 到达城市 66。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ui,Vi≤N1 \leq U_i, V_i \leq N
  • Ui≠ViU_i \neq V_i
  • 1≤Ci≤M1 \leq C_i \leq M
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页