//package shortpaths;
import java.io.*;
import java.util.*;
class commuter_pass {
public static void main(String[] args) throws IOException {
commuter_pass obj = new commuter_pass();
obj.doStuff();
}
class SortArr implements Comparator<long[]> {
@Override
public int compare(long[] o1, long[] o2) {
return (o1[1]<o2[1])?-1:((o1[1]>o2[1])?1:0);
}
}
ArrayList<Integer>[] vals;
@SuppressWarnings("unchecked")
void dijk1() {
PriorityQueue<long[]> pq = new PriorityQueue<>(new SortArr());
pq.add(new long[] {s, 0});
long[] mins = new long[graph.length];
Arrays.fill(mins, Long.MAX_VALUE);
vals = new ArrayList[graph.length];
for (int i = 0; i < vals.length; i++) {
vals[i] = new ArrayList<>();
}
while (!pq.isEmpty()) {
long[] next = pq.poll();
int pos = (int) next[0];
if (mins[pos] < next[1]) continue;
for (int[] i : graph[pos]) {
long nc = mins[pos]+i[1];
if (nc < mins[i[0]]) {
mins[i[0]] = nc;
vals[i[0]] = new ArrayList<>();
vals[i[0]].add(pos);
pq.add(new long[] {i[0], nc});
} else if (nc == mins[i[0]]) {
vals[i[0]].add(pos);
pq.add(new long[] {i[0], nc});
}
}
}
}
void recur(int val, int par) {
if (val == s) {
dijk2();
return;
}
for (int i : vals[val]) {
if (i == par) continue;
graph[i].add(new int[] {val, 0});
graph[val].add(new int[] {i, 0});
recur(i, val);
graph[i].remove(graph[i].size()-1);
graph[val].remove(graph[val].size()-1);
}
}
void dijk2() {
PriorityQueue<long[]> pq = new PriorityQueue<>(new SortArr());
pq.add(new long[] {u, 0});
long[] mins = new long[graph.length];
Arrays.fill(mins, Long.MAX_VALUE);
while (!pq.isEmpty()) {
long[] next = pq.poll();
int pos = (int) next[0];
if (mins[pos] != Long.MAX_VALUE) continue;
if (pos == v) {
ans = Math.min(ans, next[1]);
return;
}
if (next[1] > ans) return;
mins[pos] = next[1];
for (int[] i : graph[pos]) {
long nc = mins[pos]+i[1];
if (nc < mins[i[0]]) {
pq.add(new long[] {i[0], nc});
}
}
}
}
int n, m, s, t, u, v;
ArrayList<int[]>[] graph;
long ans = Long.MAX_VALUE;
@SuppressWarnings("unchecked")
private void doStuff() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
s = Integer.parseInt(st.nextToken())-1;
t = Integer.parseInt(st.nextToken())-1;
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken())-1;
v = Integer.parseInt(st.nextToken())-1;
graph = new ArrayList[n];
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int v = Integer.parseInt(st.nextToken());
graph[a].add(new int[] {b, v});
graph[b].add(new int[] {a, v});
}
br.close();
dijk1();
recur(t, -1);
System.out.println(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1398 ms |
69232 KB |
Output is correct |
| 2 |
Execution timed out |
2093 ms |
221584 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1457 ms |
64096 KB |
Output is correct |
| 2 |
Correct |
1712 ms |
78252 KB |
Output is correct |
| 3 |
Correct |
1555 ms |
70472 KB |
Output is correct |
| 4 |
Correct |
1499 ms |
68116 KB |
Output is correct |
| 5 |
Correct |
1706 ms |
78260 KB |
Output is correct |
| 6 |
Execution timed out |
2093 ms |
85024 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1608 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1398 ms |
69232 KB |
Output is correct |
| 2 |
Execution timed out |
2093 ms |
221584 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
