fork(1) download 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <queue>
  4. #include <map>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. struct E{
  9. 	long long int len,cost,oldLen;
  10. 	int to;
  11.  
  12. 	bool operator<(const E& e1)const{
  13. 		if(len!=e1.len)return len>e1.len;
  14. 		return cost>e1.cost;
  15. 	}
  16. };
  17.  
  18. long long int lens[100003];
  19. bool flag[100003];
  20. map<long long int,long long int> memo;
  21. map<int,vector<E> > cons;
  22. priority_queue<E> pq;
  23.  
  24. int main() {
  25. 	// your code goes here
  26. 	int n,m;
  27. 	long long int c1,allSum;
  28. 	cin>>n>>m>>c1;
  29.  
  30. 	for(int i=0;i<m;i++){
  31. 		E e;
  32. 		int from;
  33. 		long long int to,len;
  34. 		cin>>from>>to>>len;
  35. 		e.to=to;
  36. 		e.len=len;
  37. 		e.cost=e.len;
  38. 		cons[from].push_back(e);
  39. 		e.to=from;
  40. 		cons[to].push_back(e);
  41. 		allSum+=len;
  42. 	}
  43. 	for(int i=1;i<=n;i++){
  44. 		flag[i]=false;
  45. 	}
  46.  
  47. 	E e1;
  48. 	e1.to=1;
  49. 	e1.len=0;
  50. 	e1.oldLen=0;
  51. 	e1.cost=0;
  52. 	pq.push(e1);
  53. 	while(pq.size()>0){
  54. 		E e1=pq.top();
  55. 		pq.pop();
  56. 		cout<<"("<<e1.to<<" "<<e1.len<<" "<<e1.cost<<")"; 
  57. 		if(flag[e1.to]==false){
  58. 			flag[e1.to]=true;
  59. 			lens[e1.len]+=e1.cost;
  60. 			memo[e1.len]=e1.cost;
  61. 		}else{
  62. 			memo[e1.len]+=e1.cost;
  63. 			continue;
  64. 		}
  65.  
  66. 		for(auto it=cons[e1.to].begin();it!=cons[e1.to].end();it++){
  67. 			E e2=(*it);
  68. 			E e1a;
  69. 			e1a.to=e2.to;
  70. 			e1a.oldLen=e1.len;
  71. 			e1a.len=e1.len+e2.cost;
  72. 			e1a.cost=e2.cost;
  73. 			pq.push(e1a);
  74. 		}
  75. 	}
  76. 	long long int ans=allSum;
  77. 	allSum=0;
  78. 	for(auto it=memo.begin();it!=memo.end();it++){
  79. 		allSum+=(*it).second;
  80. 	}
  81. 	long long int lenSum=0;
  82. 	for(auto it=memo.begin();it!=memo.end();it++){
  83. 		//cout<<(*it).first<<" "<<(*it).second<<endl;
  84. 		allSum-=(*it).second;
  85. 		long long int t1=(*it).first*c1+allSum;
  86. 		cout<<(*it).first<<" "<<(*it).second<<endl;
  87. 		if(t1<ans)ans=t1;
  88. 	}
  89. 	cout<<ans<<endl;
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
stdout 
(1 0 0)(3 2 2)(2 3 1)(3 4 1)(1 4 2)(2 4 4)(4 6 3)(1 7 4)(5 8 5)(2 9 3)(2 13 5)0 0
2 2
3 1
4 7
6 3
7 4
8 5
9 3
13 5
15
https://ideone.com/0oNuqc
language:
C++ (gcc 8.3)
created:
3 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!