AT_arc078_d.[ARC078F] Mole and Abandoned Mine

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

鼹鼠决定住在一个废弃矿井中，该矿井可以表示为一个包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边的简单连通无向图。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$ ，移除这条边需要 $c_i$ 日元。

鼹鼠希望通过移除一些边，使得从顶点 $1$ 到顶点 $N$ 的路径仅有一条，并且在路径上不经过同一个顶点两次。请计算实现这一目标所需的最小资金。

输入格式

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

$N$ $M$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_M$ $b_M$ $c_M$

输出格式

请输出答案。

输入输出样例

输入#1

输出#1

输入#2
```
2 1
1 2 1
```
输出#2
```
0
```

输入#3

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491

输出#3

说明/提示

限制条件

$2 \leq N \leq 15$
$N-1 \leq M \leq N(N-1)/2$
$1 \leq a_i, b_i \leq N$
$1 \leq c_i \leq 10^6$
给定的图中不存在重边或自环
给定的图是连通图

样例解释 1

在下图中，用红色虚线表示被移除的边。按照该图的方式移除两条边，总共需要 $200$ 日元。

样例解释 2

有时从一开始，顶点 $1$ 到顶点 $N$ 的路径就只有一种。

由 ChatGPT 5 翻译

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

首页