Category Archives: 最短路

Codeforces 716D Complete The Graph (二分,最短路)

给出一张图,没有重边自环,有些边可以重新设置权值,构造一个方案使得最短路长度是L 我们可以先令可以重设置边的权 …

2016 ACM/ICPC Asia Regional Dalian Online

首先总结下这次大连网赛,总算了却了一直的担忧,把名额最少的大连打下来了。这场网赛给我的感觉就是“痛并快乐着”, …

CSU 1806 Toll (辛普森,最短路)

给出10个点的图,每条路的花费会根据时间t发生改变即:c * t + d,这个人通过每条路都不需要时间,f(t …

CSU 1808 地铁 (最短路)

有若干条地铁线路,有n个车站,m段路,第i段路处于ci铁路线,且连接着ai和bi需要ti的时间。如果某一个人从 …

UESTC 1220 The Battle of Guandu (最短路)

有两个阵营A和B,有n个村庄,m个战场,开始时m个战场上都没有士兵,每个战场对A来说有三种重要程度2、1、0, …

计蒜客 百度地图的实时路况 (分治,floyd)

百度地图的实时路况功能相当强大,能方便出行的人们避开拥堵路段。一个地区的交通便捷程度就决定了该地区的拥堵情况。 …

ZOJ 3946 Highway Project (最短路,贪心)

给出一个图, 每条边都有一个距离和花费,先计算出 sum{ 点0到i的最短距离 }, 在sum最小的情况下选出 …

Codeforces 567E President and Roads (最短路)

给出一个图,从s点走最短路到t点,判断每条边是否一定必须被走,如果不是必须减少多少边权能够变成一定被走的边. …

HDU 5669 Road (最短路,线段树)

现在有n个地点,其中某些地点之间有道路相连.有m个道路信息,每个道路信息用(a,b,c,d,w)表示,意为对任 …

hdu1142 A Walk Through the Forest (最短路径,记忆优化)

题意:一个地图,起点1,终点2,假设一个人在A点,下个点是B,如果B到终点的最短路径小于A到终点的最短路径那么 …