题目描述
- Bessie and her sister Elsie want to travel from the barn to their favorite field, such that they leave at exactly the same time from the barn, and also arrive at exactly the same time at their favorite field.
- The farm is a collection of N fields (1 <= N <= 100) numbered 1..N, where field 1 contains the barn and field N is the favorite field. The farm is built on the side of a hill, with field X being higher in elevation than field Y if X < Y. An assortment of M paths connect pairs of fields. However, since each path is rather steep, it can only be followed in a downhill direction. For example, a path
- connecting field 5 with field 8 could be followed in the 5 -> 8 direction but not the other way, since this would be uphill. Each pair of fields is connected by at most one path, so M <= N(N-1)/2.
- It might take Bessie and Elsie different amounts of time to follow a path; for example, Bessie might take 10 units of time, and Elsie 20. Moreover, Bessie and Elsie only consume time when traveling on paths between fields -- since they are in a hurry, they always travel through a field in essentially zero time, never waiting around anywhere.
- Please help determine the shortest amount of time Bessie and Elsie must take in order to reach their favorite field at exactly the same moment.
Bessie 和她的妹妹 Elsie 想从粮仓去她们最喜欢的田地, 也就是能够使她们一起从粮仓离开, 并且能同一时间到达的田地
这个农场是由 N 块 (1 <= N <= 100) 编号为 1..N 的田地构成的, 第一块田地就是粮仓, 并且第 N 块田地是她们最喜欢的田地这个农场建在山的一边, 所以, 如果 X < Y 的话则满足第 X 块田地的高度要高于第 Y 块田地的高度在这之中, 有 M 条交错纵横的路径将不同的田地连接起来不过, 显而易见的是, 因为每条路都太陡了, 所以这些小路只能沿着从高到低的方向走例如, 一条连接第 5 块田地和第 8 块田地的小路只能沿着 5 -> 8 的方向走, 而不能沿着其他方向, 因为那样会成为上坡路每两块田地最多只能有一条路径相连接, 所以一定有 M <= N(N-1)/2
有可能的是, Bessie 和 Elsie 两个人走同一条小路会耗费不同的时间; 比如, 通过同一条小路, Bessie 可能会耗费 10 个单位的时间, 而 Elsie 会耗费 20 个单位的时间此外, Bessie 和 Elsie 只会在通过连接两块田地的小路时耗费时间因为她们太匆忙了, 在穿过田地时不会耗费任何时间, 也从来不在任何地方停下来等待
现在, 请你判断出, 能够满足使 Bessie 和 Elsie 同时出发并且同时到达她们喜欢的田地的最短的时间
输入输出格式
输入格式:
- INPUT: (file meeting.in)
- The first input line contains N and M, separated by a space.
- Each of the following M lines describes a path using four integers A B C D, where A and B (with A < B) are the fields connected by the path, C is the time required for Bessie to follow the path, and D is the time required for Elsie to follow the path. Both C and D are in the range 1..100.
第一行输入 N 和 M, 中间用空格分开
接下来的 M 行, 每行有四个整型 A B C D, 其中, A 和 B(A < B)代表着两块用这条小路连接的田地, C 代表 Bessie 通过这条小路的时间, 而 D 代表 Elsie 通过这条小路的时间 C 和 D 均在 1..100 的范围之内
输出格式:
- OUTPUT (file meeting.out)
- A single integer, giving the minimum time required for Bessie and
- Elsie to travel to their favorite field and arrive at the same moment.
- If this is impossible, or if there is no way for Bessie or Elsie to reach
- the favorite field at all, output the word IMPOSSIBLE on a single line.
一个整型, 输出的是能够使两人同时出发并且同时到达目的地的最短时间, 如果没有满足条件的答案, 则输出 "IMPOSSIBLE"
输入输出样例
输入样例 #1:
- 3 3
- 1 3 1 2
- 1 2 1 2
- 2 3 1 2
输出样例 #1: 2
说明
- SOLUTION NOTES:
- Bessie is twice as fast as Elsie on each path, but if Bessie takes the
- path 1->2->3 and Elsie takes the path 1->3 they will arrive at the
- same time.
分析
拿到这道题我首先想到的是二分, 但仔细一想, 二分有两个问题: 一是这道题的答案不是单调的, 二是这道题很难判断情况的可行性
然后没有什么特别好的思路, 想到的就是图的遍历其实就代表这把所有可能的路径长度都保存下来, 最后在终点上找出相同长度的最短就可以了
BFS!
数组 bool f[cow][point][cost]表示奶牛 cow(0/1)走到 point 时花费为 cost 的可行性
写完裸的 BFS 就发现我很愉快的 TLE 了把数据下载下来运行, 电脑直接卡住了 //-_-
显然不能裸的 BFS 暴力搜索啊, 完全跑不出答案如何进行一个完美的剪枝就是问题了
声明一个变量 MinLen, 保存当前已知的可能最短的合题意的长度当更新了终点上 f 数组的值的时候, 判断是否可以更新 MinLen 的值
若当前搜到的点正在处理的长度已经大于 MinLen, 那它所带来的答案一定不是最小的, 不用将它的后继点继续入队
最后我又犯了一个错误 (背景音: 我的 AC 率啊!/ 瘫倒) 剪枝判断 (Line 40) 到底是 && 还是 || 呢? 仔细想一下, 其中一个奶牛到这里的时间超了, 但是另外一个奶牛还没有超, 这个数值仍然可能为之后带来更优的解!
(然后在我爸的注视下 AC 了~)
(从让电脑爆炸的逆天 TLE 到 4ms 通过, 美滋滋)
程序
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 100 + 1;
- const int MAXM = 5000;
- int n, m, Head[MAXN], EdgeCount = 0, MinLen = 100*5000;
- bool f[2][MAXN][100*MAXM];
- struct node
- {
- int p, t1, t2;
- };
- struct edge
- {
- int Next, Aim, Bessie, Elsie;
- }Edge[MAXM];
- void insert(int u, int v, int b, int e)
- {
- Edge[++EdgeCount] = (edge){Head[u], v, b, e};
- Head[u] = EdgeCount;
- }
- void BFS()
- {
- queue<node> Q;
- Q.push((node){1,0,0});
- while (!Q.empty())
- {
- node u = Q.front();
- Q.pop();
- for (int i = Head[u.p]; i; i = Edge[i].Next)
- {
- int v = Edge[i].Aim;
- f[0][v][u.t1+Edge[i].Bessie] = 1;
- f[1][v][u.t2+Edge[i].Elsie] = 1;
- if (v == n)
- {
- if (f[0][n][u.t1+Edge[i].Bessie] && f[1][n][u.t1+Edge[i].Bessie])
- MinLen = min(MinLen, u.t1+Edge[i].Bessie);
- if (f[1][n][u.t2+Edge[i].Elsie] && f[0][n][u.t2+Edge[i].Elsie])
- MinLen = min(MinLen, u.t2+Edge[i].Elsie);
- }
- if (u.t1+Edge[i].Bessie<MinLen || u.t2+Edge[i].Elsie<MinLen)
- Q.push((node){v,u.t1+Edge[i].Bessie,u.t2+Edge[i].Elsie});
- }
- }
- for (int i = 1; i <= 100 * 5000; i++)
- {
- if (f[0][n][i] && f[1][n][i])
- {
- cout << i << endl;
- return;
- }
- }
- cout << "IMPOSSIBLE" << endl;
- }
- int main()
- {
- freopen("meet.in","r",stdin);
- freopen("meet.out","w",stdout);
- cin >> n >> m;
- for (int i = 1; i <= m; i++)
- {
- int u, v, b, e;
- cin >> u >> v >> b >> e;
- insert(u,v,b,e);
- }
- BFS();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2488975.html