首页 > 代码库 > PAT 1030

PAT 1030

2024-07-30 16:17:01   220人阅读

　　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


联系
我们