fork download
copy 
  1. import java.awt.Point;
  2. import java.io.BufferedReader;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileReader;
  5. import java.io.FileWriter;
  6. import java.io.IOException;
  7. import java.io.InputStreamReader;
  8. import java.io.PrintWriter;
  9. import java.lang.reflect.Array;
  10. import java.math.BigInteger;
  11. import java.text.Collator;
  12. import java.util.ArrayList;
  13. import java.util.Arrays;
  14. import java.util.Collections;
  15. import java.util.Comparator;
  16. import java.util.HashMap;
  17. import java.util.LinkedList;
  18. import java.util.Queue;
  19. import java.util.Scanner;
  20. import java.util.Stack;
  21. import java.util.StringTokenizer;
  22.  
  23.  
  24.  
  25.  
  26.  class TestClass {
  27.  
  28. static int[] dist ;	
  29. static int[] vis;
  30. static ArrayList<Integer>[] resu;
  31. static int[][] graph;
  32. static int max;
  33. static int max2;
  34. static int[][] dp;
  35. static int[][] s;
  36.  
  37.  
  38.  
  39. public static int mindist(){
  40. 	   int min = Integer.MAX_VALUE;
  41. 	   int index=Integer.MAX_VALUE;
  42.  
  43. 	   for(int i=0;i<dist.length;i++){
  44.  
  45. 		   if(dist[i]<min && vis[i]!=1){
  46.  
  47. 			     min = dist[i];
  48. 			     index = i;
  49. 		   }
  50. 	   }
  51. 	   return index;
  52.  
  53. }
  54. public static int ss(){
  55. 	int index =Integer.MAX_VALUE;
  56. 	int min = Integer.MAX_VALUE;
  57.  
  58. 	for(int i=0;i<dist.length;i++){
  59.  
  60. 		  if(vis[i]!=1 && dist[i]<min){
  61.  
  62. 			    min = dist[i];
  63. 			    index =i;
  64. 		  }
  65.  
  66. 	}
  67.  
  68. 	return index;
  69.  
  70. }
  71.  
  72. public static void find(int current , ArrayList<Point>[] paths , int block1 , int block2){
  73.  
  74. 	vis[current]=1;
  75.  
  76. 	for(int i=0;i<paths[current].size();i++){
  77.  
  78. 		    int next = paths[current].get(i).x;
  79.  
  80. 		 if(vis[next]!=1){
  81.  
  82. 			if(block1== current && block2==next) continue;
  83. 			if(block1 == next && block2 == current) continue;
  84.  
  85. 			if(dist[next]> dist[current] + paths[current].get(i).y)
  86. 				dist[next]= dist[current] + paths[current].get(i).y;
  87.  
  88.  
  89. 		 }
  90.  
  91.  
  92.  
  93. 	}
  94. 	int index = ss();
  95. 	if(index!=Integer.MAX_VALUE) find(index,paths,block1,block2);
  96.  
  97. }
  98.  
  99. public static void main(String args[] ) throws IOException  {
  100.  
  101.  
  102.  
  103.  Scanner in = new Scanner(new InputStreamReader(System.in));
  104.  
  105. int n =in.nextInt();
  106. int m =in.nextInt();
  107.     @SuppressWarnings("unchecked")
  108. ArrayList<Point>[] paths = new ArrayList[n];
  109. for(int i=0;i<n;i++) paths[i] = new ArrayList<Point>();
  110.  
  111. for(int i=0;i<m;i++){
  112. 	int xx =in.nextInt();
  113. 	int yy =in.nextInt();
  114. 	int d = in.nextInt();
  115. 	paths[xx].add(new Point(yy,d));
  116. 	paths[yy].add(new Point(xx,d));
  117. }
  118. int s = in.nextInt();
  119. int d =in.nextInt();
  120. int q = in.nextInt();
  121.  
  122. for(int i=0;i<q;i++){
  123. 	int xx = in.nextInt();
  124. 	int yy = in.nextInt();
  125. 	vis = new int[n];
  126. 	dist = new int[n];
  127. 	Arrays.fill(dist, Integer.MAX_VALUE);
  128. 	dist[s]=0;
  129. 	find(s, paths, xx, yy);
  130. 	if(dist[d]!=Integer.MAX_VALUE)
  131. 	System.out.println(dist[d]);
  132. 	else
  133. 		System.out.println("Infinity");
  134.  
  135. }
  136.  
  137.  
  138.  
  139.  
  140. }
  141. }
  142.  
  143.  
Success #stdin #stdout 0.1s 380736KB
comments (?)
stdin
copy 
6 9 
0 1 1 
1 2 1 
2 3 1 
3 4 1 
4 5 1 
2 4 5 
3 5 8 
1 3 3 
0 2 4 
0 5 
9 
0 1 
1 2 
2 3 
3 4 
4 5 
2 4 
3 5 
1 3 
0 2
stdout
copy 
7
6
6
8
11
5
5
5
5
https://ideone.com/vGycl1
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!