fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4.  
  5. public class Main
  6. {
  7. 	static class node implements Comparable<node>
  8. 	{
  9. 		int goal;
  10. 		int cost;
  11.  
  12. 		public node(int goal , int cost)
  13. 		{
  14. 			this.goal = goal;
  15. 			this.cost = cost;
  16. 		}
  17.  
  18. 		public int compareTo(node n)
  19. 		{
  20. 			return cost - n.cost;
  21. 		}
  22. 	}
  23. 	static int n , m , x;
  24. 	static ArrayList<node>[] list;
  25. 	static PriorityQueue<node> pq;	//매번하게 될 듯?
  26. 	static boolean[] visit;	//매번하게 될 듯?
  27. 	static int[] value;
  28. 	static boolean arrive;	//목적지 도착 후 돌아갈 타이밍을 알기 위한 장치
  29.  
  30. 	public static void main (String[] args) throws IOException
  31. 	{
  32. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  33. 		StringTokenizer st = new StringTokenizer(br.readLine());
  34.  
  35. 		n = Integer.parseInt(st.nextToken());
  36. 		m = Integer.parseInt(st.nextToken());
  37. 		x = Integer.parseInt(st.nextToken());
  38.  
  39. 		list = new ArrayList[n+1];
  40. 		value = new int[n+1];
  41.  
  42. 		for(int i = 1 ; i <= n ; i++)
  43. 		{
  44. 			list[i] = new ArrayList<>();
  45. 			if(i != x) value[i] = Integer.MAX_VALUE;
  46. 		}
  47.  
  48. 		for(int i = 0 ; i < m ; i++)
  49. 		{
  50. 			st = new StringTokenizer(br.readLine());
  51. 			int a = Integer.parseInt(st.nextToken());
  52. 			int b = Integer.parseInt(st.nextToken());
  53. 			int c = Integer.parseInt(st.nextToken());
  54.  
  55. 			list[b].add(new node(a,c));
  56. 		}
  57.  
  58. 		for(int i = 1 ; i <= n ; i++)
  59. 		{
  60. 			Collections.sort(list[i]);
  61. 		}
  62.  
  63. 		bfs(x);
  64.  
  65. 		int max = 0;
  66. 		for(int i = 1 ; i <= n ; i++)
  67. 		{
  68. 			//System.out.println(value[i]);
  69. 			max = Math.max(value[i],max);
  70. 		}
  71. 		System.out.println(max);
  72. 	}
  73. 	public static void bfs(int start)
  74. 	{
  75. 		visit = new boolean[n+1];
  76. 		arrive = false;
  77. 		pq = new PriorityQueue<>();
  78. 		pq.add(new node(start,0));
  79.  
  80. 		while(!pq.isEmpty())
  81. 		{
  82. 			node nod = pq.poll();
  83.  
  84. 			if(visit[nod.goal]) continue;
  85. 			visit[nod.goal] = true;
  86.  
  87. 			for(int i = 0 ; i < list[nod.goal].size() ; i++)
  88. 			{
  89. 				node next = list[nod.goal].get(i);
  90.  
  91. 				if(!visit[next.goal] && value[next.goal] > value[nod.goal] + next.cost)
  92. 				{
  93. 					value[next.goal] = value[nod.goal] + next.cost;
  94. 					pq.add(new node(next.goal , value[next.goal]));
  95. 				}
  96. 			}
  97. 		}
  98. 	}
  99. }
Success #stdin #stdout 0.09s 51404KB
comments (?)
stdin
copy 
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
stdout
copy 
6
https://ideone.com/7UkFqi
language:
Java (HotSpot 12)
created:
1 year 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!