fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. public class Main
  4. {
  5. 	public static int Vertex=0,Edge=0;
  6. 	public static ArrayList<List>[] Map;
  7. 	public static int[] dist;
  8. 	public static void main(String[] args)throws IOException 
  9. 	{
  10. 		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
  11. 		StringTokenizer st = new StringTokenizer(br.readLine()," ");
  12. 		Vertex=Integer.parseInt(st.nextToken());Edge=Integer.parseInt(st.nextToken());
  13. 		int start = Integer.parseInt(br.readLine()),i=0,v1=0,v2=0,distance=0;
  14. 		Map = new ArrayList[Vertex+1];
  15. 		dist= new int[Vertex+1];
  16.  
  17. 		for(i=1;i<=Vertex;i++)
  18. 		{	
  19. 			Map[i]=new ArrayList<>();
  20. 			dist[i] = Integer.MAX_VALUE-1;
  21. 		}
  22. 		for(i=0;i<Edge;i++)
  23. 		{
  24. 			st=new StringTokenizer(br.readLine()," ");
  25. 			v1=Integer.parseInt(st.nextToken());
  26. 			v2=Integer.parseInt(st.nextToken());
  27. 			distance=Integer.parseInt(st.nextToken());
  28. 			Map[v1].add(new List(v2,distance));
  29. 		}
  30. 		Djikstra(start);
  31. 		for(i=1;i<=Vertex;i++)
  32. 		{	
  33. 			if(dist[i] != Integer.MAX_VALUE-1)
  34. 				System.out.println(dist[i]);
  35. 			else
  36. 				System.out.println("INF");
  37. 		}
  38. 	}
  39. 	public static void Djikstra(int start)
  40. 	{
  41. 		int i=0,now=0,now_dist=0,next=0,next_dist=0;
  42. 		PriorityQueue<List> pq = new PriorityQueue<>();
  43.  
  44. 		dist[start]=0;
  45. 		for(i=0;i<Map[start].size();i++)
  46. 		{	
  47. 			now=Map[start].get(i).index;
  48. 			now_dist=Map[start].get(i).dist;
  49.  
  50. 			dist[now]=now_dist;
  51. 			pq.add(new List(now,dist[now]));
  52. 		}
  53. 		while(!pq.isEmpty())
  54. 		{
  55. 			List temp = pq.poll();
  56. 			now=temp.index;
  57. 			now_dist=dist[now];
  58.  
  59. 			for(i=0;i<Map[now].size();i++)
  60. 			{
  61. 				next=Map[now].get(i).index;
  62. 				next_dist=Map[now].get(i).dist+now_dist;
  63. 				if(dist[next]>next_dist)
  64. 				{
  65. 					dist[next]=next_dist;
  66. 					pq.add(new List(next,dist[next]));
  67. 				}
  68. 			}
  69. 		}
  70. 	}
  71. }
  72. class List implements Comparable<List>
  73. {
  74. 	int index=0;
  75. 	int dist=0;
  76. 	List(int index,int dist)
  77. 	{
  78. 		this.index=index;
  79. 		this.dist=dist;
  80. 	}
  81. 	public int compareTo(List o)
  82. 	{
  83. 		return this.dist<=o.dist?-1:1;
  84. 	}
  85. }
Success #stdin #stdout 0.06s 32888KB
comments (?)
stdin
copy 
2 2
1
1 2 1
1 2 2
stdout
copy 
0
2
https://ideone.com/GCKvSg
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!