Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.StringTokenizer;
- import java.util.ArrayList;
- public class cMain implements Runnable {
- StringTokenizer st;
- BufferedReader in;
- PrintWriter out;
- ArrayList<Integer>[] graph;
- ArrayList<Integer>[] dstgraph;
- int color[];
- int n;
- int m;
- int time;
- int pr[];
- int counter;
- int answer[];
- int d[];
- int flag;
- int start, finish;
- public static void main(String[] args) {
- new Thread(new cMain()).run();
- }
- public void run() {
- try {
- in = new BufferedReader(new FileReader("shortpath.in"));
- out = new PrintWriter(new FileWriter("shortpath.out"));
- solve();
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- out.flush();
- out.close();
- }
- }
- String nextToken() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine());
- }
- return st.nextToken();
- }
- int nextInt() throws NumberFormatException, IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws NumberFormatException, IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(nextToken());
- }
- void DFSVISIT(int a) {
- color[a] = 1;
- int s = graph[a].size();
- for (int i = 0; i < s; i++) {
- int ii = graph[a].get(i);
- if (color[ii] == 1) {
- flag = 1;
- }
- if (color[ii] == 0) {
- DFSVISIT(ii);
- }
- }
- color[a] = 2;
- answer[counter] = a;
- counter++;
- }
- void DFS() {
- DFSVISIT(start);
- /*for (int i = 0; i < n; i++) {
- if (color[i] == 0) {
- DFSVISIT(i);
- if (flag == 1) {
- return;
- }
- }
- }*/
- }
- void ISS(int a) {
- for (int i = 0; i < n; i++) {
- d[i] = 1000000;
- }
- d[a] = 0;
- }
- void relax(int u, int v, int i) {
- int w = dstgraph[u].get(i);
- if (d[v] > d[u] + w) {
- d[v] = d[u] + w;
- pr[v] = u;
- }
- }
- @SuppressWarnings("unchecked")
- void solve() throws NumberFormatException, IOException {
- n = nextInt();
- m = nextInt();
- start = nextInt();
- finish = nextInt();
- start--;
- finish--;
- d = new int[n];
- color = new int[n];
- pr = new int[n];
- answer = new int[n];
- graph = new ArrayList[n];
- dstgraph = new ArrayList[n];
- for (int i = 0; i < n; i++) {
- graph[i] = new ArrayList<Integer>();
- dstgraph[i] = new ArrayList<Integer>();
- }
- for (int i = 0; i < m; i++) {
- int a, b, w;
- a = nextInt();
- b = nextInt();
- w = nextInt();
- graph[a - 1].add(b - 1);
- dstgraph[a - 1].add(w);
- }
- DFS();
- ISS(start);
- for (int i = n - 1; i != -1; i--) {
- int s = graph[answer[i]].size();
- for (int ii = 0; ii < s; ii++) {
- relax(answer[i], graph[answer[i]].get(ii), ii);
- }
- }
- if (d[finish] != 1000000) {
- out.print(d[finish]);
- } else {
- out.print("Unreachable");
- }
- }
- }
Add Comment
Please, Sign In to add comment