hdu 3873 Invade the Mars (有限制条件的最短路。。)

hdu3873题目链接

题意:n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

思路:。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解

思路倒是不难想,我在写spfa的时候也是这样想法,然后试图记录路径递归来搞。。。。。然而并不可以2333

也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。

哦对了。。。权值比较大。。。要记得开long long

 

 

 

codeforces 567 E President and Roads (优先队列+迪杰斯特拉+tarjan)

题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边.

如果是就输出yes

如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边.

对于一条边是否一定是最短路上的边,我们可以从s做一遍最短路,然后反响建边,从t再做一遍最短路.

得到两个d1,d2数组

如果一条边d1[u] + d2[v] + w(u, v) = 最短路,那这条边在最短路上的边.但是未必不能缺少.

我们还要判断这条边是否是不能缺少的.

不能缺少的意思是说,如果没有这条边,就不能构成最短路.

那么这条边一定是桥.

我们可以用tarjan算法求桥.

 

据说是水题,不过图论还没怎么刷,所以对我来说还是很有难度的.

只是基本懂了

下面的代码是我仿照其他人的代码写出来的….求不鄙视 ><