当前位置:首页 > 图论 > 最短路径 > 正文
洛谷P1629邮递员送信
2229+

题目大意:在有向图中,从A点出发,去B点,再回到A点,最短路程是多少?现在是从A点出发,分别对很多个点进行这样的操作,又如何求最短路程呢?

题目描述

有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

输入输出格式

输入格式:

第一行包括两个整数N和M。

第2到第M+1行,每行三个数字U、V、W,表示从A到B有一条需要W时间的道路。 满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。

【数据规模】

对于30%的数据,有1≤N≤200;

对于100%的数据,有1≤N≤1000,1≤M≤100000。

输出格式:

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

输入输出样例

输入样例#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

输出样例#1:

83

解题思路

把每次送东西的路程分成往返两程,如去n点,去的时候需要球1到n的最短路径;回来的时候求n到1的最短路径。其他点也是如此。1到其他各点的最短路径很容易求,但是返程怎么求呢?不难发现,只要把边反向之后,1到i的最短路径,就是原来i到1的最短路径!

程序实现

About

坚决不Copy代码!

本文标签:,,,,

洛谷P1629邮递员送信:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!