题目描述(ID:12084)
标题: 邮递员送信
标签: 图结构 最短路
详情:
有一个邮递员要送东西,邮局在结点 1。他总共要送 N-1 样东西,其目的地分别是 2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 M 条道路,通过每条道路需要一定的时间。 这个邮递员每次只能带一样东西。 求送完这 N-1 样东西平且最终回到邮局最少需要多少时间。
输入格式:
输入文件第一行包含一个正整数 N 和 M;
接下来 M 行, 每行三个正整数 U、 V、 W, 表示该条道路为从 U 到 V 的, 且通过这条道路
需要 W 的时间。满足 1≤U, V≤N,1≤W≤10000, 输入保证任意两点都能互相到达。
输出格式:
输出仅一行,包含一个整数,为最少需要的时间。
限制: 对于 30%的数据,满足 1≤N≤200。
对于 100%的数据,满足 1≤N≤1000,1≤M≤100000。
样例:

输入

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
登录并解答