首页 > 代码库 > PAT 1030
PAT 1030
dij最短路，这道题稍微麻烦一点的是如果路径长度相同，需要找到cost更小的那条路。在dij最短路中，如果更新到某个节点，发现从该路到这个节点的dist相同，且cost更小，则直接更新cost就可以了。因为只是看该节点的最短路如何，贪心就能过，不知道是不是正确的，如果我自己实现的话肯定是反过来再加一个dfs了，也比较好写。感觉C++在传值，传引用这方面更加灵活，JAVA就很不靠谱的感觉。刚看了一个文章说是scala会取代JAVA，JAVA的确是太庞大了，比起C++来说，直观感觉还是JAVA更大一点。另外JAVA写程序真没什么优势，都要写好长啊... 和C++差不太多，因为要写一个FastReader看起来就更蠢了... 但是没办法o(︶︿︶)o
首先还是再写一下dij最短路算法吧。步骤如下
1. 初始化一个dij_dist数组，数组中将start定为0，其余为MAX
2. 重复以下过程，直到所有节点都被访问过了
a. 从未访问过的节点中找到dij_dist值最小的节点，并且将它标记为访问过了
b. 更新未访问过的节点的dij_dist值，如果graph[least_idx][i] + dij_dist[least_idx] < dij_dist[i]，则更新
对dij_cost的更新放在每次更新dij_dist值的时候，如果dist值相等再比较一下cost值，并更新。
从这道题我想到了，和leetcode很不一样的是，PAT更像ACM一点，如果能够直接用数组开出来空间就不要怕浪费了，无所谓的... 不要强迫症了... 能直接贪心过的也不要管，PAT考完就好了。
对于我这种不会写JAVA的人来说还是轻松点好..
而且这道题很容易过啊= = 耗时最长的一个点才50ms
代码如下
1 import java.io.*; 2 import java.lang.reflect.Array; 3 import java.util.*; 4 5 class FastReader{ 6 BufferedReader reader; 7 StringTokenizer tokenizer; 8 9 public FastReader(InputStream stream){ 10 reader = new BufferedReader(new InputStreamReader(stream), 1 << 10); 11 tokenizer = null; 12 } 13 14 public String next(){ 15 while (tokenizer == null || !tokenizer.hasMoreTokens()){ 16 try{ 17 tokenizer = new StringTokenizer(reader.readLine()); 18 } catch (Exception e){ 19 throw new RuntimeException(e); 20 } 21 } 22 23 return tokenizer.nextToken(); 24 } 25 26 public long next_long(){ 27 return Long.parseLong(next()); 28 } 29 30 public int next_int(){ 31 return Integer.parseInt(next()); 32 } 33 } 34 35 public class Main { 36 static int[] dij_dist; 37 static int[] dij_cost; 38 39 static int[] prev; 40 static int[][] graph_cost; 41 static int[][] graph_dist; 42 static int MAX; 43 static int N, M, S, D; 44 45 static void dij_calc(){ 46 int start = S; 47 48 dij_dist = new int[N]; 49 dij_cost = new int[N]; 50 prev = new int[N]; 51 52 Arrays.fill(dij_dist, Integer.MAX_VALUE); 53 dij_dist[start] = 0; 54 dij_cost[start] = 0; 55 56 Set<Integer> done_set = new HashSet<Integer>(); 57 Set<Integer> find_set = new HashSet<Integer>(); 58 59 for (int i = 0; i < N; i++) 60 find_set.add(i); 61 62 while (!find_set.isEmpty()){ 63 Iterator<Integer> it; 64 65 it = find_set.iterator(); 66 int least_dij_dist = MAX; 67 int least_idx = 0; 68 while (it.hasNext()){ 69 int next_idx = it.next(); 70 if (dij_dist[next_idx] < least_dij_dist){ 71 least_dij_dist = dij_dist[next_idx]; 72 least_idx = next_idx; 73 } 74 } 75 76 if (least_dij_dist == MAX || least_idx == D) 77 return; 78 79 done_set.add(least_idx); 80 find_set.remove(least_idx); 81 82 it = find_set.iterator(); 83 while (it.hasNext()){ 84 int idx = it.next(); 85 if (least_dij_dist + graph_dist[least_idx][idx] < dij_dist[idx]){ 86 dij_dist[idx] = least_dij_dist + graph_dist[least_idx][idx]; 87 dij_cost[idx] = graph_cost[least_idx][idx] + dij_cost[least_idx]; 88 prev[idx] = least_idx; 89 } else if (least_dij_dist + graph_dist[least_idx][idx] == dij_dist[idx]){ 90 if (graph_cost[least_idx][idx] + dij_cost[least_idx] < dij_cost[idx]){ 91 dij_cost[idx] = graph_cost[least_idx][idx] + dij_cost[least_idx]; 92 prev[idx] = least_idx; 93 } 94 } 95 } 96 } 97 } 98 99 @SuppressWarnings("unchecked")100 public static void main(String[] args){101 FastReader reader = new FastReader(System.in);102 103 MAX = (1 << 20);104 105 N = reader.next_int();106 M = reader.next_int();107 S = reader.next_int();108 D = reader.next_int();109 110 graph_cost = new int[N][N];111 graph_dist = new int[N][N];112 113 for (int i = 0; i < N; i++){114 Arrays.fill(graph_dist[i], MAX);115 Arrays.fill(graph_cost[i], MAX);116 }117 118 for (int i = 0; i < M; i++){119 int city1, city2;120 int dist, cost;121 122 city1 = reader.next_int();123 city2 = reader.next_int();124 dist = reader.next_int();125 cost = reader.next_int();126 127 graph_dist[city1][city2] = dist;128 graph_dist[city2][city1] = dist;129 graph_cost[city1][city2] = cost;130 graph_cost[city2][city1] = cost;131 }132 133 dij_calc();134 135 Stack<Integer> ans_stack = new Stack<Integer>();136 int idx = D;137 while (idx != S){138 ans_stack.push(idx);139 idx = prev[idx];140 }141 ans_stack.push(S);142 143 while (!ans_stack.empty())144 System.out.print(ans_stack.pop() + " ");145 System.out.println(dij_dist[D] + " " + dij_cost[D]);146 }147 }
PAT 1030
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。