fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. typedef long long LL;  
  4. using namespace std;
  5.  
  6. #define fillchar(a, x) memset(a, x, sizeof(a))
  7. #define MP make_pair
  8. #define PB push_back
  9. #define endl '\n'
  10.  
  11. const long long M = (long long)1e9+7;
  12. const long long N = 1e5 + 5;
  13.  
  14. vector <pair<long long,long long> > g[N];
  15. vector <long long> sp;
  16. bool col[N];
  17.  
  18. int main()
  19. {
  20. // ios_base::sync_with_stdio(0); 
  21. cout.precision(15);
  22. cout.setf(ios::fixed);
  23.  
  24. long long t,i;
  25. cin >> t;
  26.  
  27.  
  28. while(t--)
  29. {
  30. long long a,b,c;
  31. long long n,m,k;
  32.  
  33. cin >> n >> m>>k;
  34.  
  35.  
  36. sp.resize(n);
  37.  
  38. for(i=0;i<n;i++)
  39. 	{
  40. 	g[i].clear();
  41. 	sp[i] = 0;
  42. 	col[i] = false;	
  43. 	}
  44.  
  45. for(i=0;i<m;i++)
  46. 	{
  47. 	cin >> a >> b >> c;
  48. 	a--;b--;
  49. 	g[a].PB(MP(b,c));
  50. 	g[b].PB(MP(a,c));	
  51. 	}
  52.  
  53. set <pair<long long,long long> > st;
  54. st.insert(MP(0,n-1));
  55. set <pair<long long,long long> > :: iterator it;
  56. long long ss,sh;
  57.  
  58. while(!st.empty())
  59. 	{
  60. 	 it = st.begin();
  61. 	 ss = it->second;
  62. 	 sh = it->first;
  63.  
  64. 	 st.erase(it);
  65.  
  66. 	 if(col[ss]) continue;
  67.  
  68.     col[ss] = true;
  69. 	 sp[ss] = sh;	
  70.  
  71. 	 for(i=0;i<g[ss].size();i++)
  72. 	 	st.insert(MP(sh+g[ss][i].second,g[ss][i].first));	
  73. 	}
  74.  
  75. sh = sp[0];
  76.  
  77. sort(sp.begin(),sp.end());
  78. reverse(sp.begin(),sp.end());
  79.  
  80. double A,sum = 0,mA=1e12;;
  81.  
  82. for(i=0;i<n;i++)
  83. 	sum += sp[i];
  84.  
  85. for(i=0;i<n-1;i++)		
  86. 	{
  87. 	sum -= sp[i];
  88. 	A = ((i+1)*k*1.0+sum)/(n-(i+1));	
  89. 	mA = min(mA,A);
  90. 	}
  91.  
  92. double ans = min(mA+k,(double)sh);
  93.  
  94. cout << ans << endl;
  95.  
  96. }
  97. }
Runtime error #stdin #stdout 0s 4744KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZKRaUL
language:
C++ (gcc 8.3)
created:
8 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!