Submission #2560114
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.getNewEdge(); 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; private 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)); } public List<Edge>[] getNewEdge(){ edge = null; return newEdge; } } 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 | 3912 Byte |
Status | WA |
Exec Time | 3164 ms |
Memory | 382100 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 | 113 ms | 22228 KB |
sample_2.txt | AC | 92 ms | 21716 KB |
subtask_1_1.txt | AC | 152 ms | 26520 KB |
subtask_1_10.txt | AC | 955 ms | 117644 KB |
subtask_1_11.txt | AC | 93 ms | 19668 KB |
subtask_1_2.txt | AC | 577 ms | 113932 KB |
subtask_1_3.txt | MLE | 1481 ms | 259332 KB |
subtask_1_4.txt | AC | 305 ms | 119700 KB |
subtask_1_5.txt | AC | 317 ms | 122196 KB |
subtask_1_6.txt | AC | 801 ms | 146844 KB |
subtask_1_7.txt | MLE | 1746 ms | 255224 KB |
subtask_1_8.txt | AC | 325 ms | 121828 KB |
subtask_1_9.txt | AC | 407 ms | 115960 KB |
subtask_2_1.txt | MLE | 1882 ms | 256620 KB |
subtask_2_2.txt | MLE | 1967 ms | 257440 KB |
subtask_2_3.txt | MLE | 1847 ms | 258444 KB |
subtask_2_4.txt | MLE | 1908 ms | 257064 KB |
subtask_2_5.txt | WA | 755 ms | 156896 KB |
subtask_2_6.txt | WA | 887 ms | 165556 KB |
subtask_2_7.txt | WA | 1152 ms | 168572 KB |
subtask_2_8.txt | MLE | 1902 ms | 257312 KB |
subtask_3_1.txt | TLE | 3164 ms | 340692 KB |
subtask_3_2.txt | TLE | 3164 ms | 338488 KB |
subtask_3_3.txt | TLE | 3163 ms | 322984 KB |
subtask_3_4.txt | TLE | 3162 ms | 292796 KB |
subtask_3_5.txt | TLE | 3164 ms | 319456 KB |
subtask_3_6.txt | TLE | 3163 ms | 382100 KB |
subtask_3_7.txt | TLE | 3164 ms | 343740 KB |
subtask_3_8.txt | TLE | 3164 ms | 343692 KB |