同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22075_邮递员送信

2022-5-16 18:21| 发布者: Hocassian| 查看: 24| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-8950690044100-Problem List-采集的数据-后羿采集器.html

Pro.ID

22075

Title

邮递员送信

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22075

AC

64

Submit

178

Ratio

35.96%

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

有一个邮递员要送东西（命苦），邮局在节点1。他总共要送 N-1 件东西，其目的地分别是节点2~N。由于这个城市的交通比较烦忙（中国没有哪个城市的交通是不繁忙的了），因此所有的道路都是单行的（这个嘛，就有点夸张了），共有M条道路，通过每条道路需要一定的时间（当然啦，堵车要消耗不少时间）。这个邮递员每次只能带一件东西（真有性格）。求送完这 N-1 件东西并且最终回到邮局最少需要多少时间？

输入

输入的第一行是两个整数 N 和 M，1 <= N <= 1000， 1 <= M <= 100000

接下来M行，每行3个正整数 U ，V ，W ，表示该条道路是从节点U到节点V的，且通过这条道路需要W的时间。满足 1 <= U, V <= N ， 1 <= W <= 10000 ，保证任意两点都能互相到达。

输出

Description

有一个邮递员要送东西（命苦），邮局在节点1。他总共要送 N-1 件东西，其目的地分别是节点2~N。由于这个城市的交通比较烦忙（中国没有哪个城市的交通是不繁忙的了），因此所有的道路都是单行的（这个嘛，就有点夸张了），共有M条道路，通过每条道路需要一定的时间（当然啦，堵车要消耗不少时间）。这个邮递员每次只能带一件东西（真有性格）。求送完这 N-1 件东西并且最终回到邮局最少需要多少时间？

Input

输入的第一行是两个整数 N 和 M，1 <= N <= 1000， 1 <= M <= 100000

接下来M行，每行3个正整数 U ，V ，W ，表示该条道路是从节点U到节点V的，且通过这条道路需要W的时间。满足 1 <= U, V <= N ， 1 <= W <= 10000 ，保证任意两点都能互相到达。

Output

输出一行，包含一个整数，为最少需要的时间。

Sample Input

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

Sample Output

83

Author

样例输入

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

样例输出

83

提示

作者

最新评论

相关分类

返回顶部