Atcoder ABC340 D - Super Takahashi Bros.

本文主要是介绍Atcoder ABC340 D - Super Takahashi Bros.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Super Takahashi Bros.（超级高桥兄弟）

时间限制：2s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

【输入格式】

【输出格式】

【样例1】

【样例输入1】

5
100 200 3
50 10 1
100 200 5
150 1 2

【样例输出1】

350

【样例说明1】

【样例2】

【样例输入2】

10
1000 10 9
1000 10 10
1000 10 2
1000 10 3
1000 10 4
1000 10 5
1000 10 6
1000 10 7
1000 10 8

【样例输出2】

90

【样例3】

【样例输入3】

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

【样例输出3】

5000000000

【解题思路】

老汉使用到的是Dijkstra+优先队列优化的解题方式

代码注释有详细过程

【代码】

package ABC340_D_SuperTakahashiBros;import java.util.*;public class Main {// 存放起始点到该点的最短时间static long[] dp;// 存放该下标对应点可直接到达的下一个点static int[][] ne;// 存放该下标对应点可直接到达的下一个点所需花费的时间static int[][] val;// 点的个数static int n;public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();// ne[i][0]代表i的下一点i+1，ne[i][1]代表可以直接到达的另一个点ne = new int[n][2];// 对应ne所需花费的时间val = new int[n][2];dp = new long[n];// 为ne、val数组赋值，起始点为0for (int i = 0; i < n - 1; i++) {int v1 = scan.nextInt();int v2 = scan.nextInt();int c = scan.nextInt() - 1;ne[i][0] = i + 1;ne[i][1] = c;val[i][0] = v1;val[i][1] = v2;}// 将dp赋值为long最大值Arrays.fill(dp, Long.MAX_VALUE);// 起始点到起始点花费最短时间为0dp[0] = 0;// 利用优先队列优化dij，本题求最小值，采用小根排序，降低时间复杂化度为O(nlogn)PriorityQueue<Node> set = new PriorityQueue<>(new Comparator<Node>() {@Overridepublic int compare(Node o1, Node o2) {if (o1.val > o2.val) {return 1;} else if (o1.val == o2.val) {return 0;} else {return -1;}}});// 向队列添加起始点0set.add(new Node(0, 0));// dij求最短路径while (!set.isEmpty()) {Node cur = set.poll();for (int i = 0; i < 2; i++) {int n = ne[cur.nx][i];int v = val[cur.nx][i];if (dp[n] > cur.val + v) {dp[n] = cur.val + v;set.add(new Node(dp[n], n));}}}// 输出1~n即下标0~n-1的最短用时System.out.println(dp[n - 1]);scan.close();}public static class Node {// 从起点到当前点的最短用时long val;// 可直接到达的下一点int nx;public Node(long val, int nx) {this.val = val;this.nx = nx;}}
}

这篇关于Atcoder ABC340 D - Super Takahashi Bros.的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---