hdu3592 World Exhibition--单源最短路径&差分约束
发布日期:2021-10-03 20:32:11
浏览次数:2
分类:技术文章
本文共 3202 字,大约阅读时间需要 10 分钟。
原题链接:
一:原题内容
Problem Description
Nowadays, many people want to go to Shanghai to visit the World Exhibition. So there are always a lot of people who are standing along a straight line waiting for entering. Assume that there are N (2 <= N <= 1,000) people numbered 1..N who are standing in the same order as they are numbered. It is possible that two or more person line up at exactly the same location in the condition that those visit it in a group. There is something interesting. Some like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of X (1 <= X <= 10,000) constraints describes which person like each other and the maximum distance by which they may be separated; a subsequent list of Y constraints (1 <= Y <= 10,000) tells which person dislike each other and the minimum distance by which they must be separated. Your job is to compute, if possible, the maximum possible distance between person 1 and person N that satisfies the distance constraints.
Input
First line: An integer T represents the case of test. The next line: Three space-separated integers: N, X, and Y. The next X lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= N. Person A and B must be at most C (1 <= C <= 1,000,000) apart. The next Y lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= C. Person A and B must be at least C (1 <= C <= 1,000,000) apart.
Output
For each line: A single integer. If no line-up is possible, output -1. If person 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between person 1 and N.
Sample Input
14 2 11 3 82 4 152 3 4
Sample Output
19
二:分析理解
一次AC的题!
对于X行的来说:B-A<=C
对于Y行的来说:B-A>=C
最后:(i) -( i-1)>=0,其中2<=i<=N
因为题意要求是最大值所以转化一下就是:
B-A<=C;
A-B<=-C;
(i-1)-(i)<=0;
三:AC代码
#include#include #include using namespace std;struct Edge{ int v; int w; int next;};Edge edge[30005];int cnt[1005];int sta[1005];bool visited[1005];int dis[1005];int head[1005];int num;int T;int N, X, Y;int A, B, C;void AddEdge(int u, int v, int w){ edge[num].v = v; edge[num].w = w; edge[num].next = head[u]; head[u] = num++;}int Spfa(){ dis[1] = 0; int top = 1; sta[top] = 1; visited[1] = 1; while (top) { int u = sta[top--]; visited[u] = 0; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (dis[v] > dis[u] + edge[i].w) { dis[v] = dis[u] + edge[i].w; if (!visited[v]) { sta[++top] = v; visited[v] = 1; cnt[v]++; } if (cnt[v] > N) return -1; } } } if (dis[N] == 99999999) return -2; return dis[N];}int main(){ scanf("%d", &T); while (T--) { num = 0; memset(head, -1, sizeof(head)); memset(cnt, 0, sizeof(cnt)); memset(visited, 0, sizeof(visited)); fill(dis, dis + 1005, 99999999); scanf("%d%d%d", &N, &X, &Y); while (X--) { scanf("%d%d%d", &A, &B, &C); AddEdge(A, B, C); } while (Y--) { scanf("%d%d%d", &A, &B, &C); AddEdge(B, A, -C); } for (int i = 2; i <= N; i++) AddEdge(i, i - 1, 0); printf("%d\n", Spfa()); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/51043451 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月23日 22时15分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
hdu 6165(dfs or bfs or tarjan+topsort)
2019-04-26
hdu 6168(stl)
2019-04-26
hdu 6170(正则表达式)
2019-04-26
排列组合 "n个球放入m个盒子m"问题 总结(转)
2019-04-26
codeforces845C(stl)
2019-04-26
图的几种存储方式(邻接矩阵+邻接表+vector)
2019-04-26
[LeetCode] 67. 二进制求和(简单模拟二进制求和)
2019-04-26
HDU1233(基础最小生成树 prim和 kruskal)
2019-04-26
「图解」ThreadLocal 在并发问题中的应用
2019-04-26
终于找到可以一文多发的平台了!
2019-04-26
IntelliJ IDEA 2019 快捷键终极大全,速度收藏!
2019-04-26
世界很大,先从这几个公众号看起!
2019-04-26
真实的上海IT圈:张江男vs漕河泾男
2019-04-26
你还在认为 count(1) 比 count(*) 效率高?
2019-04-26
Master、Slave等术语将不能在未来的Linux代码中使用
2019-04-26
在Redis中设置了过期时间的Key,需要注意哪些问题?
2019-04-26
干掉 GuavaCache:Caffeine 才是本地缓存的王
2019-04-26
Spring Boot 2.x基础教程:EhCache缓存的使用
2019-04-26
如何让你的Nginx 提升10倍性能?
2019-04-26
神奇的 SQL,Group By 真扎心,原来是这样!
2019-04-26