Guest User

Untitled

a guest
Jul 15th, 2018
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.99 KB | None | 0 0
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.FileReader;
  4. import java.io.FileWriter;
  5. import java.io.IOException;
  6. import java.io.PrintWriter;
  7. import java.util.StringTokenizer;
  8. import java.util.ArrayList;
  9.  
  10. public class cMain implements Runnable {
  11. StringTokenizer st;
  12. BufferedReader in;
  13. PrintWriter out;
  14.  
  15. ArrayList<Integer>[] graph;
  16. ArrayList<Integer>[] dstgraph;
  17.  
  18. int color[];
  19.  
  20. int n;
  21. int m;
  22. int time;
  23. int pr[];
  24. int counter;
  25. int answer[];
  26. int d[];
  27. int flag;
  28. int start, finish;
  29.  
  30. public static void main(String[] args) {
  31. new Thread(new cMain()).run();
  32. }
  33.  
  34. public void run() {
  35. try {
  36. in = new BufferedReader(new FileReader("shortpath.in"));
  37. out = new PrintWriter(new FileWriter("shortpath.out"));
  38. solve();
  39. } catch (Exception e) {
  40. e.printStackTrace();
  41. } finally {
  42. out.flush();
  43. out.close();
  44. }
  45. }
  46.  
  47. String nextToken() throws IOException {
  48. while (st == null || !st.hasMoreTokens()) {
  49. st = new StringTokenizer(in.readLine());
  50. }
  51. return st.nextToken();
  52. }
  53.  
  54. int nextInt() throws NumberFormatException, IOException {
  55. return Integer.parseInt(nextToken());
  56. }
  57.  
  58. long nextLong() throws NumberFormatException, IOException {
  59. return Long.parseLong(nextToken());
  60. }
  61.  
  62. double nextDouble() throws NumberFormatException, IOException {
  63. return Double.parseDouble(nextToken());
  64. }
  65.  
  66. void DFSVISIT(int a) {
  67. color[a] = 1;
  68. int s = graph[a].size();
  69. for (int i = 0; i < s; i++) {
  70. int ii = graph[a].get(i);
  71. if (color[ii] == 1) {
  72. flag = 1;
  73. }
  74. if (color[ii] == 0) {
  75.  
  76. DFSVISIT(ii);
  77. }
  78.  
  79. }
  80. color[a] = 2;
  81.  
  82. answer[counter] = a;
  83. counter++;
  84. }
  85.  
  86. void DFS() {
  87. DFSVISIT(start);
  88. /*for (int i = 0; i < n; i++) {
  89. if (color[i] == 0) {
  90. DFSVISIT(i);
  91. if (flag == 1) {
  92. return;
  93. }
  94. }
  95. }*/
  96. }
  97.  
  98. void ISS(int a) {
  99. for (int i = 0; i < n; i++) {
  100. d[i] = 1000000;
  101. }
  102. d[a] = 0;
  103. }
  104.  
  105. void relax(int u, int v, int i) {
  106. int w = dstgraph[u].get(i);
  107. if (d[v] > d[u] + w) {
  108. d[v] = d[u] + w;
  109. pr[v] = u;
  110. }
  111. }
  112.  
  113. @SuppressWarnings("unchecked")
  114. void solve() throws NumberFormatException, IOException {
  115. n = nextInt();
  116. m = nextInt();
  117. start = nextInt();
  118. finish = nextInt();
  119. start--;
  120. finish--;
  121.  
  122. d = new int[n];
  123. color = new int[n];
  124. pr = new int[n];
  125. answer = new int[n];
  126. graph = new ArrayList[n];
  127. dstgraph = new ArrayList[n];
  128. for (int i = 0; i < n; i++) {
  129. graph[i] = new ArrayList<Integer>();
  130. dstgraph[i] = new ArrayList<Integer>();
  131. }
  132. for (int i = 0; i < m; i++) {
  133. int a, b, w;
  134.  
  135. a = nextInt();
  136. b = nextInt();
  137. w = nextInt();
  138. graph[a - 1].add(b - 1);
  139. dstgraph[a - 1].add(w);
  140.  
  141. }
  142.  
  143. DFS();
  144. ISS(start);
  145.  
  146. for (int i = n - 1; i != -1; i--) {
  147. int s = graph[answer[i]].size();
  148.  
  149. for (int ii = 0; ii < s; ii++) {
  150.  
  151. relax(answer[i], graph[answer[i]].get(ii), ii);
  152.  
  153. }
  154.  
  155. }
  156. if (d[finish] != 1000000) {
  157. out.print(d[finish]);
  158. } else {
  159. out.print("Unreachable");
  160. }
  161.  
  162. }
  163. }
Add Comment
Please, Sign In to add comment