当前位置:首页 > 图论 > 最短路径 > 正文
洛谷P1342请柬
2166+

题目大意:与邮递员送信一样的题目,只是数据范围大了:在有向图中,从A点出发,去B点,再回到A点,最短路程是多少?现在是从A点出发,分别对很多个点进行这样的操作,又如何求最短路程呢?

题目描述

在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实,他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站,他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的:所有的线路都是单向的,连接两个站点。公共汽车离开起始点,到达目的地之后又空车返回起始点。学生每天早上从总部出发,乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是,学生所需的公交费用的总和最小是多少。

输入输出格式

输入格式:

第1行有两个整数n、m(1<=n,m<=1000000),n是站点的个数,m是线路的个数。

然后有m行,每行描述一个线路,包括3个整数,起始点,目的地和价格。

总部在第1个站点,价钱都是整数,且小于1000000000。

输出格式:

输出一行,表示最小费用。

输入输出样例

输入样例#1:

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

输出样例#1:

210

说明

【注意】

此题数据规模较大,需要使用较为高效的算法,此题不设小规模数据分数。

解题思路

把每次送东西的路程分成往返两程,如去n点,去的时候需要球1到n的最短路径;回来的时候求n到1的最短路径。其他点也是如此。1到其他各点的最短路径很容易求,但是返程怎么求呢?不难发现,只要把边反向之后,1到i的最短路径,就是原来i到1的最短路径!注意:需要使用long long类型。如果需要更快,可以加些优化。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

洛谷P1342请柬:等您坐沙发呢!

发表评论

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