题目链接:https://vjudge.net/contest/543015
A-单源最短路径(弱化版)
这题没什么要讲的,纯模板,SPFA和Dijkstra都可以过,细心敲代码和调试即可。
std如下:
1 | //SPFA |
B-单源最短路径(标准版)
同A题,模板,不过SPFA无法通过此题,会超时。
因此可以用堆优化版本的Dijkstra。
std如下:
1 | //Dijkstra 堆优化版本 |
C-租用游艇
简化题意,已知任意两点间的费用,求1→n的最小费用。
这题首先要看懂什么是半矩阵,
对于样例给的半矩阵:
1 | 5 15 |
还原为矩阵:
1 | 0 5 15 |
读入的时候处理好即可,算法用SPFA或Dijkstra均可。
std如下:
1 | //SPFA |
D-Heat Wave G
本题似乎和A没有区别?
其实有的,不过大同小异,换汤不换药。
区别在于A为有向图,D为无向图,A求s到任意点,D求s到t。
同样的,SPFA和Dijkstra都能过。
std如下:
1 | //SPFA |
E-采购特价商品
依然是一道纯模板。
本体没有给出路径长度,需要根据给出的坐标计算,算好直接用即可。
同样是一道SPFA和Dijkstra都能过的题目。
std如下:
1 | //SPFA |
F-Mzc和体委的争夺战
本题似乎和A没有区别?(×2)
只改为了无向图,且只求1→n的最短路(即本题的最短时间)。
SPFA和Dijkstra均可。
std如下:
1 | //SPFA |
G-Cow Party S
本题稍稍提高了点难度,要求来回的最短路径长度,并且进一步求所有牛的最短路径中最长的长度。
为方便跑算法,图建两层,一层是从x到每头牛农场的,一层是每头牛农场到x的。
即要多建一个反向图。
这样跑两次算法时都可以从x出发,跑出来的结果一个为从x到每头牛农场的,一个为每头牛农场到x。
std如下:
1 | //SPFA |
H-医院设置
终于来了,优美的Floyd
实在没找到裸的模板……
本题要找到一点使得所有点到此点的距离*人数最小。
这时就需要用到任意两点间的距离,即多源最短路。
本题比较特殊,也可以不用Floyd
然后枚举设置点求出此时的每个点距离*人数的和,求最小即可。
std如下:
1 | //Floyd |