- 一、题目内容
- 二、题目分析
- 代码
一、题目内容
题目描述
小 tim 在游乐场，有一天终于逃了出来！但是不小心又被游乐场的工作人员发现了…所以你的任务是安全地把小 tim 护送回家。但是，A 市复杂的交通状况给你出了一大难题。
A 市一共有 n 个路口，m 条单行马路。但是，每条马路都只有一段时间是开放的。为了安全，你必须选择一条护送路线，使得小 tim 在路上的时间最短，即到家的时刻减去离开游乐场的时刻最短。
输入格式
第一行 44 个数，分别是 n,m,s,t。基地在路口 s，码头在路口 t。
接下来 mm 行每行 55 个数 x,y,b,e,c 表示一条 x 路口到 y 路口的单行线，在 b 时刻到 e 时刻之间开放，需要 c 的时间通过这条路（必须保证行进在路中间时，路一直开放，否则小 tim 会被捉住）。两个路口之间可能会有多条道路。一开始的时刻是 0（当然，你可以不用马上出发，在基地多呆一段时间）。
如果不存在任何一种方案使得小 tim 能成功到达码头，输出 Impossible。
输出格式
一行，为小 tim 在路上停留的最短时间。
输入输出样例
输入
4 5 1 4
1 2 0 1 1
1 2 0 1 2
1 3 1 3 2
2 4 3 4 1
3 4 3 4 1
输出
3
题解基本都是dijkstra或者spfa而我还不想写而诞生的题解
观察数据后可以发现，这个题给出的时间最大值为10000，这个数值并不是很大，换言之，我们可以直接遍历时间，然后遍历每一个点，判断当前时间是否可以从某条边到达这个点，如果可以到达，就将这个时间点设置为到达该点的最小时间。然后一直重复这个操作直到到达t为止。
但是通过上面的操作我们只能得到到达的最早时间点t，而题目的要求是最短在路上停留的时间，所以我们还需要一个时间记录数组tim，专门用来记录i时间到达j点的最晚出发时间，显而易见，这个数字应该越大路上的时间就越短。
接下来就只需要一边遍历所有时间点，一边更新最晚的到达时间，最后将两个时间相减就是正确答案。
至于不能到达的情况，只需要将ans一开始设置为一个超过最大时间的数字，如果这个数字没有被更新的话，就说明无解。
这个题我一直在寻思能不能停在某一个点，结果是确实可以，但题目中并没有说，卡我了半天。
代码
写了四重循环，时间复杂度应该是O(T * m) 其中T为到达t的最终时间，m为边数
#include#include #include #include #include #define ll long long using namespace std; struct line { ll x; ll y; ll b; ll e; ll c; }p[1005]; ll n, m, s, t, tim[105][10005], ans = 10005, fin = 0; vector gra[105], mir[105][105]; bool arr[105][10005]; int main() { cin >> n >> m >> s >> t; for (int i = 1; i <= m; i++) { //输入数据 cin >> p[i].x >> p[i].y >> p[i].b >> p[i].e >> p[i].c; if (p[i].c <= p[i].e - p[i].b) { gra[p[i].y].push_back(p[i].x); //建图 mir[p[i].x][p[i].y].push_back(i);//记录两点之间对应的边 } fin = max(fin, p[i].e); } //这里的数组arr用来判断时间为i的时候是否能到达j for (int i = 0; i <= 10000; i++) { arr[s][i] = true; tim[s][i] = i; } for (int i = 1; i <= 10000; i++) { for (int j = 1; j <= n; j++) { if (j == s) continue; arr[j][i] = arr[j][i - 1];//数组arr用来判断时间为i的时候是否能到达j tim[j][i] = tim[j][i - 1];//数组tim用来记录i时间能到达j点的最晚出发时间 for (int k = 0; k < gra[j].size(); k++) { int f = gra[j][k]; for (int h = 0; h < mir[f][j].size(); h++) { int num = mir[f][j][h];//获取当前两个端点的对应边的序号 ll b = p[num].b, e = p[num].e, c = p[num].c; //如果可以到达当前点j if (i <= e && i - c >= b) { arr[j][i] |= arr[f][i - c]; tim[j][i] = max(tim[j][i], tim[f][i - c]); } //如果已经可以到达最终点t if (j == t && arr[j][i]) { ans = min(i - tim[j][i], ans); } } } } } if (ans == 10005) cout << "Impossible"; else cout << ans; return 0; }
