首页 > 试题广场 >

邮递员送信

[编程题]邮递员送信
  • 热度指数：931 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}某城市共有 n 个路口与 m 条 单向 道路（交通繁忙，均为单行道）。其中 1 号路口为邮局，2 \sim n 号路口各有一件包裹待投递。

\hspace{15pt}邮递员一次只能携带一件包裹，每次从邮局取件后出发，沿道路送达对应目的地后 必须返回邮局 才能取下一件。求完成所有 n-1 件投递并最终回到邮局所需的 最短总时间。

输入描述:
\hspace{15pt}第一行输入两个整数 n,m\ \left(1 \leqq n \leqq 10^3,\ 1 \leqq m \leqq 10^5\right) —— 路口数量与道路数量。 
\hspace{15pt}接下来 m 行，每行输入三个整数 u_i,v_i,w_i\ \left(1 \leqq u_i,v_i \leqq n;\ 1 \leqq w_i \leqq 10^4\right)，表示一条从 u_i 单向通往 v_i 的道路，耗时为 w_i。 
\hspace{15pt}保证任意两点间 互相可达。


输出描述:
\hspace{15pt}输出一个整数，代表完成全部投递并返回邮局的最少总时间。
示例1

输入

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
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 56浏览

热门推荐

相关试题

邮递员送信

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号