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

AT_abc317_c.[ABC317C] Remembering the Days

普及-

通过率：0%

AC君温馨提醒

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

题目描述

在某地有 NN 个编号为 11 到 NN 的城市，以及 MM 条编号为 11 到 MM 的道路。

第 ii 条道路连接城市 AiA_i 和城市 BiB_i，是双向的，道路长度为 CiC_i。

你可以从任意一个城市出发，每经过一个城市后不能再次经过同一个城市。请你求出在满足上述条件下，经过的道路长度之和的最大可能值。

输入格式

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

NN MM
A1A_1 B1B_1 C1C_1
⋮\vdots
AMA_M BMB_M CMC_M

输出格式

请输出答案。

输入输出样例

  • 输入#1

    4 4
1 2 1
2 3 10
1 3 100
1 4 1000

    输出#1

    1110

  • 输入#2

    10 1
5 9 1

    输出#2

    1

  • 输入#3

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

    输出#3

    20

说明/提示

限制条件

  • 2≤N≤102 \leq N \leq 10
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • (Ai,Bi)(A_i, B_i) 互不相同
  • 1≤Ci≤1081 \leq C_i \leq 10^8
  • 所有输入均为整数

样例解释 1

如果按照 4→1→3→24 \to 1 \to 3 \to 2 的顺序移动，经过的道路长度之和为 11101110。

样例解释 2

可能存在没有道路连接的城市。

样例解释 3

图

由 ChatGPT 4.1 翻译

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

首页