吐槽
滚动

2017 C语言积分赛 热身赛 E题 愤怒的瓦里安 题解

题目描述

传奇国王,暴风城主瓦里安·乌瑞恩的儿子安度因又跑到酒馆里和人打牌,还用的是十分肮脏的套牌(脏牧去死啦)。瓦里安听了十分愤怒,掰了筷子就杀了过去。安度因十分慌张,连忙找一起打牌的萨尔帮忙。充满绿色能量的萨尔答应帮安度因破坏一条道路来帮他开溜。但是智商为0的安度因并不知道到底能拖延多长时间。好吧,你写个程序帮他算算咯。(已知萨尔的智商很高,破坏的道路能最大程度上拖延瓦里安的到来)

输入输出格式

输入格式:

第一行有两个用空格隔开的数n和m,分别表示道路节点的数量以及道路的数量。道路节点用数字1至n标识,瓦里安的出发地暴风城在节点1,安度因打牌的酒馆在节点n。

接下来的m行中每行包含三个用空格隔开的数u,v和w。这些数字表示在节点u和节点v中间有一条道路,并且花费w的时间通过。

输出格式:

输出瓦里安到达酒馆所需要的最短时间。

输入输出样例

输入样例#1: 

输出样例#1: 

说明

对于100%的数据,1<=n<=1000,1<=m<=n*(n-1)/2,1<=u,v<=n,1<=w<=1000。

对于本样例,原本走1->2->8->6->10为最短路,时间为21。但萨尔破坏了6->10的路径,使得最短路变为了1->2->8->5->10,时间变为74。可以证明破坏其它道路时所得到的最短路径长度均小于本方案。

一眼看去,感觉就是个图论题,于是写了个spfa,发现不对啊,这咋和样例不一样呢?再看一眼题目,发现可以删边,题目实际上是求删任意一条边后最短路的最大值。于是mengbier,过了半小时才发现一个神解法:先求一遍最短路,记录其路径,然后枚举路径上的每条边做删除处理,再求最短路的最大值。可以证明删除非最短路的边时对最短路无影响。

那么贴code。

 

Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment