fork download 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <queue>
  4. #include <map>
  5. #include <set>
  6. #include <vector>
  7. using namespace std;
  8.  
  9. struct E{
  10. 	long long int len,cost,oldLen;
  11. 	int from,to;
  12.  
  13. 	bool operator<(const E& e1)const{
  14. 		if(len!=e1.len)return len>e1.len;
  15. 		return cost>e1.cost;
  16. 	}
  17. };
  18.  
  19. struct E2{
  20. 	int from,to;
  21. 	bool operator<(const E2& e2)const{
  22. 		if(from!=e2.from)return from<e2.from;
  23. 		return to<e2.to;
  24. 	}
  25. };
  26.  
  27. long long int lens[100003];
  28. map<long long int,long long int> memo,memo2;
  29. set<E2> cons2;
  30. bool flag[100003];
  31. map<int,vector<E> > cons;
  32. priority_queue<E> pq;
  33.  
  34.  
  35. int main() {
  36. 	// your code goes here
  37. 	int n,m;
  38. 	long long int c1,allSum;
  39. 	cin>>n>>m>>c1;
  40. 	allSum=0;
  41. 	for(int i=0;i<m;i++){
  42. 		E e;
  43. 		int from;
  44. 		long long int to,len;
  45. 		cin>>from>>to>>len;
  46. 		e.to=to;
  47. 		e.len=len;
  48. 		e.cost=e.len;
  49. 		cons[from].push_back(e);
  50. 		e.to=from;
  51. 		cons[to].push_back(e);
  52. 		allSum+=len;
  53. 	}
  54. 	for(int i=1;i<=n;i++){
  55. 		lens[i]=-1;
  56. 	}
  57. 	lens[0]=0;
  58. 	E e1;
  59. 	e1.from=0;
  60. 	e1.to=1;
  61. 	e1.len=0;
  62. 	e1.oldLen=0;
  63. 	e1.cost=0;
  64. 	pq.push(e1);
  65. 	while(pq.size()>0){
  66. 		E e1=pq.top();
  67. 		pq.pop();
  68. 		if(lens[e1.to]==-1){
  69. 			lens[e1.to]=e1.len;
  70. 			memo[e1.len]+=e1.cost;
  71. 			memo2[e1.len]+=e1.cost;
  72. 		}else if(e1.oldLen<=lens[e1.to]){
  73. 			E2 e2;
  74. 			e2.from=e1.from;
  75. 			e2.to=e1.to;
  76. 			if(cons2.find(e2)!=cons2.end())continue;
  77. 			e2.from=e1.to;
  78. 			e2.to=e1.from;
  79. 			cons2.insert(e2);
  80. 			memo2[lens[e1.to]]+=e1.cost;
  81.  
  82. 			continue;
  83. 		}else{
  84. 			continue;
  85. 		}
  86.  
  87. 		for(auto it=cons[e1.to].begin();it!=cons[e1.to].end();it++){
  88. 			E e2=(*it);
  89. 			E e1a;
  90. 			e1a.from=e1.to;
  91. 			e1a.to=e2.to;
  92. 			e1a.oldLen=e1.len;
  93. 			e1a.len=e1.len+e2.cost;
  94. 			e1a.cost=e2.cost;
  95. 			pq.push(e1a);
  96. 		}
  97. 	}
  98. 	long long int ans=allSum;
  99. 	long long int lenSum=0;
  100. 	for(auto it=memo.begin();it!=memo.end();it++){
  101. 		//cout<<(*it).first<<" "<<(*it).second<<endl;
  102. 		lenSum=(*it).first;
  103. 		allSum-=memo2[(*it).first];
  104. 		long long int s0=lenSum*c1+allSum;
  105. 		if(s0<ans)ans=s0;
  106. 		//cout<<"("<<s0<<" "<<lenSum<<" "<<allSum<<")";
  107. 		//cout<<(*it).first<<" "<<(*it).second<<endl;
  108. 	}
  109. 	cout<<ans<<endl;
  110. 	return 0;
  111. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
54 61 20983
10 42 87903
22 14 11822
5 53 57569
13 27 29736
32 50 14462
10 11 40714
51 10 25235
16 27 20546
29 51 88212
44 23 40619
2 50 7571
42 9 82705
27 39 20182
2 3 61654
4 22 52371
38 53 91934
21 31 87689
28 20 52885
42 7 61075
53 24 26219
36 26 80119
34 22 62246
33 2 51534
35 46 40168
33 22 27769
46 38 71255
24 19 82511
2 40 69048
53 49 58249
17 37 82764
5 17 99276
42 35 68596
1 15 35130
38 42 73893
7 51 25010
22 37 79128
11 12 68794
2 41 16792
16 7 69414
19 4 43985
44 21 7912
53 8 27604
26 54 66918
36 53 71999
36 45 60906
24 16 6350
27 35 54697
21 27 85577
20 6 14914
17 43 77141
52 18 67694
15 7 31420
52 27 68028
22 53 89890
20 37 4810
48 46 47769
25 32 18812
6 53 97991
27 47 91648
30 21 37708
30 16 33050
stdout 
3229622
https://ideone.com/fahKSJ
language:
C++ (gcc 8.3)
created:
2 days 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!