[Link] https://www.acmicpc.net/problem/1956
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
String[] line = getLine();
int max = Integer.MAX_VALUE;
int v = toi(line[0]), e = toi(line[1]);
int[][] dis = new int[v][v];
int[][] floyd = new int[v][v];
for(int i = 0; i < v; i++) {
Arrays.fill(floyd[i], max);
floyd[i][i] = 0;
}
for(int i = 0; i < e; i++) {
line = getLine();
int a = toi(line[0]) - 1, b = toi(line[1]) - 1, c = toi(line[2]);
dis[a][b] = c;
floyd[a][b] = Math.min(floyd[a][b], c);
}
for(int mid = 0; mid < v; mid++) {
for(int from = 0; from < v; from ++) {
for(int to = 0; to < v; to++) {
if(floyd[from][mid] != max && floyd[mid][to] != max
&& floyd[from][to] > floyd[from][mid] + floyd[mid][to]) floyd[from][to] = floyd[from][mid] + floyd[mid][to];
}
}
}
int ans = max;
for(int i = 0; i < v; i++) {
for(int j = 0; j < v; j++) {
if(i == j) continue;
if(floyd[i][j] != max && floyd[j][i] != max) ans = Math.min(ans, floyd[i][j] + floyd[j][i]);
}
}
print(ans == max ? -1 : ans);
}
static class Edge{
int from;
int to;
int dis;
public Edge(int from, int to, int dis) {
this.from = from;
this.to = to;
this.dis = dis;
}
}
static int toi(String s) { return Integer.parseInt(s); }
static String[] getLine() throws IOException { return br.readLine().split(" "); }
static <T> void print(T s) { System.out.print(s); }
}
dijkstra solution(TLE time out)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] line = getLine();
int v = toi(line[0]), e = toi(line[1]);
ArrayList<ArrayList<int[]>> al = new ArrayList<>(); // 0 :
int[][] dis = new int[v][v];
int[][] dijk = new int[v][v];
for(int i = 0; i < v; i++) {
Arrays.fill(dijk[i], Integer.MAX_VALUE);
dijk[i][i] = 0;
}
for(int i = 0; i < v; i++) al.add(new ArrayList<int[]>()); // 0: to 1: dis
for(int i = 0; i < e; i++) {
line = getLine();
int a = toi(line[0]) - 1, b = toi(line[1]) - 1, c = toi(line[2]);
al.get(a).add(new int[]{b, c});
dis[a][b] = c;
}
PriorityQueue<int[]> pq = new PriorityQueue<>((l, r) -> l[1] - r[1]);
for(int start = 0; start < v; start++) {
pq.clear();
pq.add(new int[]{start, 0});
while(!pq.isEmpty()) {
int[] cur = pq.poll();
int curIdx = cur[0], curDis = cur[1];
for(int[] arr : al.get(curIdx)) {
if(dijk[start][arr[0]] > curDis + arr[1]) {
dijk[start][arr[0]] = curDis + arr[1];
pq.add(new int[]{arr[0], dijk[start][arr[0]]});
}
}
}
}
int ans = Integer.MAX_VALUE;
for(int i = 0; i < v; i++) {
for(int j = 0; j < v; j++) {
if(dis[j][i] != 0 && dijk[i][j] != Integer.MAX_VALUE) ans = Math.min(ans, dis[j][i] + dijk[i][j]);
}
}
print(ans == Integer.MAX_VALUE ? -1 : ans);
}
static int toi(String s) { return Integer.parseInt(s); }
static String[] getLine() throws IOException { return br.readLine().split(" "); }
static <T> void print(T s) { System.out.print(s); }
}