深圳好蜘蛛网站建设公司,广州市 网站建设建设,招远网站建设哪家专业,枣庄机关建设网站Last Train#xff08;最后一班火车#xff09;
时间限制#xff1a;2s 内存限制#xff1a;1024MB
【原题地址】
所有图片源自Atcoder#xff0c;题目译文源自脚本Atcoder Better!
点击此处跳转至原题
【问题描述】 【输入格式】 【输出格式】 【样例1】
【样例输入…Last Train最后一班火车
时间限制2s 内存限制1024MB
【原题地址】
所有图片源自Atcoder题目译文源自脚本Atcoder Better!
点击此处跳转至原题
【问题描述】 【输入格式】 【输出格式】 【样例1】
【样例输入1】
6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1【样例输出1】
55
56
58
60
17【样例说明1】 【样例2】
【样例输入2】
5 5
1000000000 1000000000 1000000000 1000000000 1 5
5 9 2 6 2 3
10 4 1 6 2 3
1 1 1 1 3 5
3 1 4 1 5 1【样例输出2】
1000000000000000000
Unreachable
1
Unreachable【样例说明2】 【样例3】
【样例输入3】
16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12【样例输出3】
720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828【解题思路】
老汉使用到的是DP优先队列优化的解题方式
本题是求每个站点到N站点的最晚出发时间。 利用站点关系从N站点开始递推回去最晚出发时间值存在与该站点最晚一班车发车时间和下一站点到N站点最晚发车时间减去该站点到下一站点的途中用时c之间的最小值利用优先队列取大根减少没必要的计算优化时间复杂度最后判断该站到N站点最晚出发时间是否被赋值是则输出该值否则输出Unreachable
代码注释有详细过程
【代码】
package ABC342_E_LastTrain;import java.io.*;
import java.util.*;public class Main {static VectorNode[] g;static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer st new StreamTokenizer(br);public static int readInt() throws IOException {st.nextToken();return (int) st.nval;}public static void main(String[] args) throws IOException {int n readInt();int m readInt();// 用于存放对应的上一站点到达当前点的数据g new Vector[n 1];for (int i 0; i n 1; i) {g[i] new Vector();}// 存入对应站点数据for (int i 0; i m; i) {int l readInt();int d readInt();int k readInt();int c readInt();int A readInt();int B readInt();g[B].add(new Node(A, l, d, k, c));}// 存放从下标位置站点出发到N站点的最晚出发时间long[] dp new long[n 1];// 默认值为-1Arrays.fill(dp, -1);// 创建优先队列创建为大根堆以出发到达N站点的出发时间为比较值PriorityQueuePair que new PriorityQueue(new ComparatorPair() {Overridepublic int compare(Pair o1, Pair o2) {if (o1.val o2.val)return -1;else if (o1.val o2.val)return 1;return 0;}});// dp起始点为N站点que.add(new Pair((long) 4e18, n));while (!que.isEmpty()) {Pair cur que.poll();// 如果当前dp值已经赋值跳过由于优先队列排序第一次赋值已经是最大值最晚出发时间if (dp[cur.x] ! -1)continue;// 为当前dp值赋值dp[cur.x] cur.val;// 遍历上一站点求上一站点出发到N站点的最晚出发时间for (int i 0; i g[cur.x].size(); i) {Node a g[cur.x].get(i);// 该站点到N点的最晚出发时间减去上一站点到该站点的c值求出上一站点允许的最晚出发时间long ms cur.val - a.c;// 当这个最晚出发时间在上一站点的出发时刻表中时求出符合上一站点的最晚出发时间if (ms a.l) {ms Math.min((ms - a.l) / a.d, (a.k - 1)) * a.d a.l;que.add(new Pair(ms, a.A));}}}// 如果dp未赋值则说明无法到达N站点有则输出该dp值for (int i 1; i n; i) {if (dp[i] -1)pw.println(Unreachable);elsepw.println(dp[i]);}pw.flush();pw.close();br.close();}// 存放x站点到N站点所需时间public static class Pair {long val;int x;public Pair(long val, int x) {this.val val;this.x x;}}// 存放到上一站点对应数据public static class Node {int A;long l;long d;long k;long c;public Node(int A, long l, long d, long k, long c) {this.A A;this.l l;this.d d;this.k k;this.c c;}}}
