-
Notifications
You must be signed in to change notification settings - Fork 3
/
AllPairsPath.java
120 lines (100 loc) · 3.63 KB
/
AllPairsPath.java
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// Using Reader class
import java.io.*;
import java.util.*;
public class AllPairsPath {
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
}
public static void main(String[] args) throws IOException {
Reader sc = new Reader();
PrintWriter writer = new PrintWriter(System.out);
int INF = 1000000000;
while (true) {
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
if (n == 0 && m == 0 && q == 0) {
writer.flush();
return;
}
AdjacencyMatrix graph = new AdjacencyMatrix(n);
while (m-- > 0)
graph.connect(sc.nextInt(),sc.nextInt(),sc.nextInt());
graph.doFloydWarshall();
while (q-- > 0) {
int sp = graph.D[sc.nextInt()][sc.nextInt()];
if (sp == INF)
writer.println("Impossible");
else if (sp == -INF)
writer.println("-Infinity");
else
writer.println(sp);
}
writer.println();
}
}
}
class AdjacencyMatrix {
public int[][] matrix;
public int numVertices;
public int[][] D;
public int INF;
public AdjacencyMatrix (int V) {
numVertices = V;
matrix = new int[V][V];
INF = 1000000000;
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
matrix[i][j] = (i == j) ? 0 : INF;
}
public void connect (int a, int b, int w) { matrix[a][b] = Math.min(matrix[a][b], w); }
public void doFloydWarshall () {
D = new int[numVertices][numVertices];
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
D[i][j] = matrix[i][j];
for (int k = 0; k < numVertices; k++)
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
D[i][j] = Math.min(D[i][j], (D[i][k] == INF || D[k][j] == INF) ? INF : D[i][k]+D[k][j]);
// Negative cycles
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
for (int k = 0; k < numVertices && D[i][j] != -INF; k++)
if (D[i][k] != INF && D[k][j] != INF && D[k][k] < 0)
D[i][j] = -INF;
}
}