| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 697854 | vjudge1 | Evacuation plan (IZhO18_plan) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.stream.IntStream.*;
/********************************************/
public class treearray {
public static void main(String[] args) throws IOException {
new Solution().run();
}
}
/********************************************/
class Solution {
final FastScanner scanner = new FastScanner();
final PrintWriter out = new PrintWriter(System.out);
final int mod = (int) 1e9+7;
final int[] dx = {1, 0, -1, 0};
final int[] dy = {0, 1, 0, -1};
int maxn = (int) 3e5+10;
int[] npp, d, p, size;
List<Pair<Integer, Pair<Integer, Integer>>> e = new ArrayList<>();
HashSet<Integer>[] set;
void solve() throws IOException {
int n = scanner.nextInt(), m = scanner.nextInt();
init(n); d = new int[n+1];
fill(d, mod);
p = new int[n+1]; size = new int[n+1];
for (int i = 0; i<=n; i++) {
p[i] = i;
size[i] = 1;
}
for (int i = 0; i<m; i++) {
int x = scanner.nextInt(), y = scanner.nextInt(), w = scanner.nextInt();
g[x].add(new Pair(y, w));
g[y].add(new Pair(x, w));
}
PriorityQueue<Pair<Integer, Integer>> q = new PriorityQueue<>(Comparator.comparingInt((p) -> p.first));
int k = scanner.nextInt();
npp = new int[k];
for (int i = 0; i<k; i++) {
npp[i] = scanner.nextInt();
d[npp[i]] = 0;
q.add(mp(-d[npp[i]], npp[i]));
}
while (!q.isEmpty()) {
var curr = q.poll();
int dist = curr.first, v = curr.second;
if (dist>d[v]) continue;
for (var node : g[v]) {
int to = node.first, cost = node.second;
if (d[to]>d[v]+cost) {
d[to] = d[v]+cost;
q.add(mp(-d[to], to));
}
}
}
int Q = scanner.nextInt();
var ans = new int[Q];
for (int i = 1; i<=Q; i++) {
int x = scanner.nextInt(), y = scanner.nextInt();
set[x].add(i-1);
set[y].add(i-1);
}
for (int i = 1; i<=n; i++) {
for (var node : g[i]) {
e.add(new Pair(min(d[i], d[node.first]), mp(i, node.first)));
}
}
e.sort((x, y)->(x.first-y.first));
for (int i = e.size()-1; i>=0; i--) {
int cost = e.get(i).first;
int a = find(e.get(i).second.first), b = find(e.get(i).second.second);
if (a == b) continue;
if (set[a].size()<set[b].size()) {
int temp = a;
a = b;
b = temp;
}
for (var ind : set[b]) {
if (set[a].size()>0) {
ans[ind] = cost;
set[a].add(ind);
} else {
set[a].add(ind);
}
}
p[b] = a;
}
StringBuilder builder = new StringBuilder();
for (int i : ans)
builder.append(i).append(' ');
out.println(builder);
}
int find(int u) {
if (u == p[u]) return u;
return p[u] = find(p[u]);
}
void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void swap(long[] a, int i, int j) {
long temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void swap(HashMap<Integer, Integer>[] a, int i, int j) {
HashMap<Integer, Integer> temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Pair<Integer, Integer> mp(int x, int y) {
return new Pair(x, y);
}
List<Pair<Integer, Integer>>[] g;
boolean[] was;
void init(int n) {
g = new ArrayList[n+1];
was = new boolean[n+1];
set = new HashSet[n+1];
for (int i = 0; i<=n; i++) {
g[i] = new ArrayList<>();
set[i] = new HashSet<>();
}
}
void run() throws IOException {
int t = 1;
while (t-->0) {
solve();
}
out.flush();
}
}
class Pair<First, Second> {
First first;
Second second;
public Pair(First first, Second second) {
this.first = first;
this.second = second;
}
}
class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int nextInt() throws IOException {
int x = 0, sign = 1;
char c = (char) br.read();
while ((c < '0' || c > '9') && c != '-') {
c = (char) br.read();
}
if (c == '-') {
sign = -1;
c = (char) br.read();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c & 15);
c = (char) br.read();
}
return sign * x;
}
long nextLong() throws IOException {
long x = 0, sign = 1;
char c = (char) br.read();
while ((c < '0' || c > '9') && c != '-') {
c = (char) br.read();
}
if (c == '-') {
sign = -1;
c = (char) br.read();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c & 15);
c = (char) br.read();
}
return sign * x;
}
String next() throws IOException {
StringBuilder sb = new StringBuilder();
char c = (char) br.read();
while (c == ' ' || c == '\n' || c == '\r') {
c = (char) br.read();
}
while (c != ' ' && c != '\n' && c != '\r') {
sb.append(c);
c = (char) br.read();
}
return sb.toString();
}
int[] readArray(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long[] readLong(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
}