fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.Scanner;
  7. import java.util.StringTokenizer;
  8.  
  9.  
  10. class Main{
  11. 	static class V{
  12. 		int det;
  13. 		int val;
  14. 		public V(int det, int val) {
  15. 			super();
  16. 			this.det = det;
  17. 			this.val = val;
  18. 		}
  19. 	}
  20. 	public static void main(String[] args) throws NumberFormatException, IOException {
  21. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  22. 		StringTokenizer stk = new StringTokenizer(br.readLine());
  23. 		int n=Integer.parseInt(stk.nextToken());
  24. 		int m=Integer.parseInt(stk.nextToken());
  25. 		int st=Integer.parseInt(br.readLine());
  26.  
  27. 		int dist[] = new int[n+1];
  28. 		int visited[] = new int[n+1];
  29.  
  30. 		ArrayList<V>[] list=new ArrayList[n+1];
  31. 		for (int i = 0; i < list.length; i++) {
  32. 			list[i] = new ArrayList<V>();
  33. 		}
  34.  
  35. 		for (int i = 0; i < m; i++) {
  36. 			stk=new StringTokenizer(br.readLine());
  37. 			list[Integer.parseInt(stk.nextToken())].add(new V(Integer.parseInt(stk.nextToken()),Integer.parseInt(stk.nextToken())));
  38. 		}
  39. 		for (int i = 1; i < n+1; i++) {
  40. 			dist[i]=987654321;
  41. 		}
  42. 		for (int i = 0; i < list[st].size(); i++) {
  43. 			int det = list[st].get(i).det;
  44. 			int val = list[st].get(i).val;
  45. 			dist[det]=val;
  46. 		}
  47. 		dist[st]=0;
  48. 		visited[st]=1;
  49. 		for (int i =0 ; i < n-1 ; i++) {
  50. 			int min_index=st;
  51. 			int min=987654321;
  52. 			for (int j = 1; j < n+1; j++) {
  53. 				if(visited[j]!=1 && min > dist[j]) {
  54. 					min=dist[j];
  55. 					min_index=j;
  56. 				}
  57. 			}
  58. 			for (int j = 0; j < list[min_index].size(); j++) {
  59. 				int det = list[min_index].get(j).det;
  60. 				int val = list[min_index].get(j).val;
  61. 				if(visited[det]==0 &&dist[min_index]+val<dist[det])
  62. 					dist[det]=dist[min_index]+val;
  63. 			}
  64. 			visited[min_index]=1;
  65.  
  66. 		}
  67. 		for (int i = 1; i < n+1; i++) {
  68. 			if(dist[i]==987654321)
  69. 				System.out.println("INF");
  70. 			else {
  71. 				System.out.println(dist[i]);				
  72. 			}
  73. 		}
  74. 	}
  75. }
Success #stdin #stdout 0.06s 32976KB
comments (?)
stdin
copy 
2 2
1
1 2 1
1 2 2
stdout
copy 
0
2
https://ideone.com/BXz0pV
language:
Java (12.0.1)
created:
4 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!