fork(2) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<utility>
  6. #include<algorithm>
  7. #include<iomanip>
  8. #include<functional>
  9. #include<limits>
  10. #include<memory>
  11. #include<cstdlib>
  12. #include<cassert>
  13. #include<cctype>
  14. #include<cfloat>
  15. #include<stack>
  16. #include<queue>
  17. #include<deque>
  18. #include<iterator>
  19. #include<list>
  20. #include<vector>
  21. #include<map>
  22. #include<set>
  23. #include<numeric>
  24. #include<ctime>
  25. #include<sstream>
  26.  
  27. using namespace std;
  28.  
  29. // ***COMMONLY USED MACROS***
  30. #define MOD 1000000007
  31. #define pb push_back
  32. #define pob pop_back
  33. #define pf push_front
  34. #define pof pop_front
  35. #define minr min_element
  36. #define maxr max_element
  37. #define mh make_heap
  38. #define ph push_heap
  39. #define poh pop_heap
  40. #define Sd(n) scanf("%d",&n)
  41. #define Pd(n) printf("%d\n",n)
  42. #define mp(i,j) make_pair(i,j)
  43. #define Sld(n) scanf("%lld",&n)
  44. #define Pld printf("%lld\n",n)
  45. #define Ss(s) scanf("%s\n",s)
  46. #define Ps(s) printf("%s\n",s)
  47. #define forn(i,n) for(int i=0;i<int(n);i++)
  48. #define ford(i,n) for(int i=int(n);i>=0;i--)
  49. #define all(a) a.begin(),a.end()
  50. #define set(a,x) memset(a,x,sizeof(a))
  51. #define mod 10000007
  52. //  ***FEW TYPEDEFINES**
  53. typedef unsigned long long int uint64;
  54. typedef long long int int64;
  55. typedef pair<int64,int64> pii;
  56.  
  57. const long double pi = 3.1415926535897932384626433832795;
  58. const long double eps = 1e-9;
  59.  
  60. int g[1001][1001];
  61. const int INF = 1000000000; 
  62. int cost[1001];
  63.  
  64. int main(){
  65. 	int n,t,m,a,b,c;
  66. 	cin>>t;//test cases
  67. 	while(t--){
  68. 	cin>>n>>m;//vertices and edges
  69. //initializing
  70. 	for(int i=0;i<n;i++){
  71. 		cost[i]=INF;
  72. 	for(int j=0;j<n;j++){
  73. 	g[i][j]=INF;}}	
  74. //input source dest cost
  75. 	for(int i=0;i<m;i++){
  76. 		cin>>a>>b>>c;
  77. 		a--;
  78. 		b--;
  79. 		g[a][b]=c;
  80. 		g[b][a]=c;
  81. 	}
  82.  
  83. cost[0] = 0;
  84. //algo
  85. for(int i=0;i<n;i++){
  86. 	for(int j=0;j<n;j++){
  87. 		if(g[i][j]<cost[j])
  88. 		cost[j]=g[i][j];
  89. 	}
  90. }
  91. int64 ans=0;
  92. //calculating cost of the entire path
  93. for(int i=0;i<n;i++)
  94. ans=ans+cost[i];
  95. cout<<ans<<endl;
  96. }
  97.  
  98. return 0;}
  99.  
Success #stdin #stdout 0s 6648KB
comments (?)
stdin
copy 
1
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 
6
https://ideone.com/uLJpJn
language:
C++ 4.3.2 (gcc-4.3.2)
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!