Submission #2560097
Source Code Expand
import java.util.*; public class Main{ static List<Edge>[] edge; static int[][] vmax; static int n,m; static ArrayDeque<Integer> q = new ArrayDeque<>(); public static void main(String[] args){ Scanner sc = new Scanner(System.in); int inf = (int)1e9; n = Integer.parseInt(sc.next()); m = Integer.parseInt(sc.next()); Prim pr = new Prim(n); for(int i=0; i<m; i++){ int a = Integer.parseInt(sc.next())-1; int b = Integer.parseInt(sc.next())-1; int c = Integer.parseInt(sc.next()); pr.addEdge(a, b, c); } //ここから引く long all = pr.prim(); //System.out.println(all); edge = pr.newEdge; vmax = new int[n][n]; for(int i=0; i<n; i++){ Arrays.fill(vmax[i], -1); } vmax = new int[n][n]; for(int i=0; i<n; i++){ Arrays.fill(vmax[i],-1); } int q = Integer.parseInt(sc.next()); for(int i=0; i<q; i++){ int s = Integer.parseInt(sc.next())-1; int t = Integer.parseInt(sc.next())-1; System.out.println(all - maxv(s,t)); } } public static int maxv(int s, int t){ int max = 0; q.clear(); q.add(s); boolean[] used = new boolean[n]; while(q.size() != 0){ int now = q.pollFirst(); used[now] = true; for(int i=0; i<edge[now].size(); i++){ Edge e = edge[now].get(i); vmax[s][e.to] = Math.max(vmax[s][now], e.cost); if(vmax[s][e.to] == -1){ vmax[s][e.to] = max; vmax[e.to][s] = max; } if(vmax[s][t] != -1){ return vmax[s][t]; } if(!used[e.to]){ q.add(e.to); } } } return vmax[s][t]; } } class Prim{ public static int n; private static List<Edge>[] edge; public static List<Edge>[] newEdge; public static final int inf = (int)10e9; public Prim(int n){ this.n = n; edge = new List[n]; newEdge = new List[n]; for(int i=0; i<n; i++){ edge[i] = new ArrayList<>(); newEdge[i] = new ArrayList<>(); } } public long prim(){ boolean[] check = new boolean[n]; Queue<Edge> q = new PriorityQueue<>(); q.add(new Edge(0,0,0));//だみー long res = 0; while(!q.isEmpty()){ Edge e = q.poll(); if(check[e.to]){ continue; } check[e.to] = true; res += e.cost; //newEdgeに追加 addNewEdge(e.from, e.to, e.cost); q.addAll(edge[e.to]); } return res; } public void addEdge(int from, int to, int cost){ edge[from].add(new Edge(from, to, cost)); edge[to].add(new Edge(to, from, cost)); } private void addNewEdge(int from, int to, int cost){ newEdge[from].add(new Edge(from, to, cost)); newEdge[to].add(new Edge(to, from, cost)); } } class Edge implements Comparable<Edge>{ public int from = 0; public int to = 0; public int cost = 0; public Edge(int from, int to, int cost) { this.from = from; this.to = to; this.cost = cost; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | sca1l |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 3930 Byte |
Status | WA |
Exec Time | 3163 ms |
Memory | 412336 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 300 | 0 / 200 | ||||||||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All | sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 95 ms | 19540 KB |
sample_2.txt | AC | 94 ms | 19412 KB |
subtask_1_1.txt | AC | 147 ms | 24916 KB |
subtask_1_10.txt | AC | 1044 ms | 166768 KB |
subtask_1_11.txt | AC | 91 ms | 18772 KB |
subtask_1_2.txt | AC | 657 ms | 211516 KB |
subtask_1_3.txt | MLE | 1663 ms | 256408 KB |
subtask_1_4.txt | AC | 351 ms | 167896 KB |
subtask_1_5.txt | AC | 376 ms | 167160 KB |
subtask_1_6.txt | MLE | 925 ms | 255708 KB |
subtask_1_7.txt | MLE | 1670 ms | 259136 KB |
subtask_1_8.txt | AC | 333 ms | 168648 KB |
subtask_1_9.txt | AC | 436 ms | 168208 KB |
subtask_2_1.txt | MLE | 2085 ms | 279064 KB |
subtask_2_2.txt | MLE | 2061 ms | 280472 KB |
subtask_2_3.txt | MLE | 2077 ms | 281300 KB |
subtask_2_4.txt | MLE | 2121 ms | 279748 KB |
subtask_2_5.txt | WA | 844 ms | 230884 KB |
subtask_2_6.txt | WA | 1017 ms | 237964 KB |
subtask_2_7.txt | MLE | 1419 ms | 317312 KB |
subtask_2_8.txt | MLE | 2120 ms | 278004 KB |
subtask_3_1.txt | TLE | 3160 ms | 410644 KB |
subtask_3_2.txt | TLE | 3160 ms | 412336 KB |
subtask_3_3.txt | TLE | 3163 ms | 368496 KB |
subtask_3_4.txt | TLE | 3158 ms | 357176 KB |
subtask_3_5.txt | TLE | 3160 ms | 316340 KB |
subtask_3_6.txt | TLE | 3163 ms | 368768 KB |
subtask_3_7.txt | TLE | 3161 ms | 408088 KB |
subtask_3_8.txt | TLE | 3161 ms | 410772 KB |