UVALive

2023-04-09 23:25| 来源: 网络整理| 查看: 265

UVALive - 4618 Wormholes(负环) 原创

暗金色 2023-04-07 13:39:44 博主文章分类：ACM-图论-最短路 ©著作权

文章标签 i++ #include #define 文章分类 Html/CSS 前端开发

©著作权归作者所有：来自51CTO博客作者暗金色的原创作品，请联系作者获取转载授权，否则将追究法律责任

题目大意：给出出发点和终点和m个虫洞(虫洞的出发点，终点，生成时间和花费时间)，问从起点到终点花费的最小时间

解题思路：关键是有负环，所以直接跑最短路算法的话会TLE，所以负环要处理一下但是这个负环又不是负环，因为负环到一定程度的话，就会消失。比如，到达时间小于虫洞的生成时间，那么负环就消失了，也就是说，负环内的点满足的最优情况就是到达时间刚好等于生成时间所以，先找出负环，接着判断一下这个负环内的能节省的最多时间，然后将所有点都减去那个时间，那么负环就消失了具体看代码

#include #include #include #include using namespace std; #define N 110 #define INF 0x3f3f3f3f struct Point{ int x, y, z; }s1, s2; struct wormhole{ Point s, t; int start, cost; }W[N]; int n, source, sink; int dis[N][N]; int distance(int i, int j) { int x = W[i].t.x - W[j].s.x; int y = W[i].t.y - W[j].s.y; int z = W[i].t.z - W[j].s.z; return ceil(sqrt(1.0 * x * x + 1.0 * y * y + 1.0 * z * z)); } void init() { scanf("%d%d%d%d%d%d%d", &s1.x, &s1.y, &s1.z, &s2.x, &s2.y, &s2.z, &n); source = 0; sink = n + 1; W[0].s = s1; W[0].t = s1; W[0].start = -INF; W[0].cost = 0; W[sink].s = s2; W[sink].t = s2; W[sink].start =-INF; W[sink].cost = 0; for (int i = 1; i

【本文地址】

UVALive

UVALive

今日新闻

推荐新闻