fork(2) download
copy 
  1.  
  2.  
  3.  
  4.  
  5. 			import java.io.*;
  6. import java.util.*;
  7. 			class CSTREET
  8. 			{
  9. 				public static void main(String args[])
  10. 				throws IOException
  11. 				{
  12. 					BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  13. 					int t=Integer.parseInt(br.readLine());
  14. 					while(t--!=0)
  15. 					{
  16. 						HashMap<Integer,ArrayList<String>> Map=new HashMap<Integer,ArrayList<String>>();
  17. 						ArrayList<Integer> V=new ArrayList<Integer>();
  18.  
  19.  
  20. 						int p=Integer.parseInt(br.readLine());
  21. 						int n=Integer.parseInt(br.readLine());
  22. 						int m=Integer.parseInt(br.readLine());
  23. 						for(int i=0;i<m;i++)
  24. 						{
  25. 							String in[]=br.readLine().split("\\s(?=\\S*$)");
  26. 							int cost=p*Integer.parseInt(in[1]);
  27. 							if(!Map.containsKey(cost))
  28. 							{
  29. 								ArrayList<String> al=new ArrayList<String>();
  30. 								al.add(in[0]);
  31. 								Map.put(cost, al);
  32. 							}
  33. 							else
  34. 							{
  35. 								ArrayList<String> get=Map.get(cost);
  36. 								get.add(in[0]);
  37. 								Map.put(cost,get);
  38. 							}
  39. 						}
  40. 						//iterate
  41. 						long sum=0;
  42.  
  43. 						Map<Integer,ArrayList<String>> map = new TreeMap<Integer,ArrayList<String>>(Map);//sorting by keys
  44.  
  45. 						Iterator it=map.entrySet().iterator();
  46. 						while(it.hasNext())
  47. 						{
  48. 							Map.Entry<Integer, ArrayList<String>> pairs=(Map.Entry<Integer, ArrayList<String>>)it.next() ;
  49. 							int cost=pairs.getKey();
  50. 							ArrayList<String> edges=pairs.getValue();// there can be multiple edges having single cost
  51.  
  52. 							Iterator<String> i=edges.iterator();
  53. 							while(i.hasNext())
  54. 							{
  55. 								String edge= i.next();
  56. 								String s[]=edge.split(" ");
  57. 								int u=Integer.parseInt(s[0]);
  58. 								int v=Integer.parseInt(s[1]);
  59.  
  60. 								if(V.contains(u) && V.contains(v))// neglect this edge if part of same set V
  61. 								{
  62. 									continue;
  63. 								}
  64. 								else if( V.contains(u) && !V.contains(v) )
  65. 								{
  66. 									V.add(v);
  67. 									sum+=cost;
  68. 								}
  69. 								else if( !V.contains(u) && V.contains(v) )
  70. 								{
  71. 									V.add(u);
  72. 									sum+=cost;
  73. 								}
  74. 								else if(  !V.contains(u) && !V.contains(v) )
  75. 								{
  76. 									V.add(u);
  77. 									V.add(v);
  78. 									sum+=cost;
  79. 								}
  80.  
  81. 							}
  82.  
  83. 						}
  84.  
  85. 						System.out.println(sum);
  86.  
  87. 					}
  88. 				}
  89. 			}
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
1
2
5
7
1 2 1
2 3 2
2 4 6
5 2 1
5 1 3
4 5 2
3 4 3
stdout
copy 
12
https://ideone.com/1jkKLl
language:
Java (12.0.1)
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!