题目详情题解（0）讨论（0）提交记录（0）

AT_ttpc2019_f.Road Construction

通过率：0%

AC君温馨提醒

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

题目描述

有 NN 个城市，编号为 11 到 NN。最初，这些城市之间没有任何道路。

现在有 MM 个修建道路的方案，第 ii 个方案表示以 cic_i 日元的费用，从城市 sis_i 到城市 tit_i（si<tis_i < t_i）修建一条单向道路。

你可以选择其中一些方案，使得城市 ww 能到达城市 xx，并且城市 yy 能到达城市 zz。

请你求出满足上述条件所需的最小总费用。如果不存在这样的方案，请输出 Impossible。

输入格式

输入通过标准输入给出，格式如下：

NN MM ww xx yy zz
c1c_1 s1s_1 t1t_1
⋮\vdots
cMc_M sMs_M tMt_M

输出格式

输出使得城市 ww 能到达城市 xx，且城市 yy 能到达城市 zz 所需的最小总费用。如果不存在这样的方案，则输出 Impossible。

输入输出样例

  • 输入#1

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

    输出#1

    6

  • 输入#2

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

    输出#2

    Impossible

  • 输入#3

    5 8
1 3 2 5
42 2 3
32 2 4
12 3 5
94 1 4
21 4 5
79 1 2
22 1 5
90 1 3

    输出#3

    133

说明/提示

限制条件

  • 所有输入均为整数。
  • 4≤N≤1054 \leq N \leq 10^5
  • 2≤M≤2×1052 \leq M \leq 2 \times 10^5
  • 1≤w<x≤N1 \leq w < x \leq N
  • 1≤y<z≤N1 \leq y < z \leq N
  • 1≤ci≤1091 \leq c_i \leq 10^9
  • 1≤si<ti≤N1 \leq s_i < t_i \leq N
  • w,x,y,zw, x, y, z 互不相同。
  • 对于 i≠ji \ne j，有 (si,ti)≠(sj,tj)(s_i, t_i) \ne (s_j, t_j)。

样例解释 1

  • 选择修建方案 1,3,4,61, 3, 4, 6，总费用为 66 日元，这是最小值。

样例解释 2

  • 无论如何选择修建方案，都无法使指定的城市间互相可达。

由 ChatGPT 4.1 翻译

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

首页