fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template<class X, class Y> void mini(X &x, const Y &y){
  6. 	x = min(x, y);
  7. }
  8.  
  9. template<class X, class Y> void maxi(X &x, const Y &y){
  10. 	x = max(x, y);
  11. }
  12.  
  13. typedef string str;
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. typedef __int128 i128;
  17. typedef double db;
  18. typedef long double ld;
  19. typedef pair<int, int> pii;
  20. typedef pair<ll, ll> pll;
  21. typedef pair<ld, ld> pldld;
  22. typedef pair<db, db> pdd;
  23. typedef pair<char, char> pcc;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vl;
  26. typedef vector<char> vc;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29. typedef vector<vector<int>> vii;
  30. typedef vector<vector<ll>> vll;
  31. typedef vector<vector<char>> vcc;
  32. typedef map<int, int> mpii;
  33. typedef map<ll, ll> mpll;
  34. typedef set<int> si;
  35. typedef set<ll> sl;
  36. typedef complex<ld> cd;
  37.  
  38. #define se second
  39. #define fi first
  40. #define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
  41. #define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
  42. #define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
  43. #define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
  44. #define Fore(x, a) for(auto x: a)
  45. #define pb push_back
  46. #define pf push_front
  47. #define ppb pop_back
  48. #define ppf pop_front
  49. #define ins insert
  50. #define era erase
  51. #define upb upper_bound
  52. #define lwb lower_bound
  53. #define all(a) a.begin(), a.end()
  54.  
  55. const db PI = acos(-1);
  56. const ll inf = 1e18 + 1;
  57. const int mod = 1e9 + 7;
  58. const int maxn = 2e5 + 1;
  59.  
  60. int n, m, V;
  61. int s, t;
  62. vpii g[maxn];
  63. ld d[maxn];
  64.  
  65. signed main(){
  66. 	ios_base::sync_with_stdio(false);
  67. 	cin.tie(nullptr); cout.tie(nullptr);
  68. 	if(fopen("D:/inp.txt", "r"))
  69. 		freopen("D:/inp.txt", "r", stdin),
  70. 		freopen("D:/out.txt", "w", stdout);
  71. 	cin >> n >> m >> V;
  72. 	For(i, 1, m, 1){
  73. 		int u, v, w; cin >> u >> v >> w;
  74. 		g[u].pb({v, w}); g[v].pb({u, w});
  75. 	}
  76. 	cin >> s >> t;
  77. 	fill(d, d + maxn, 1e18);
  78. 	priority_queue<pair<ld, int>> pq;
  79. 	d[s] = 0; pq.push({0, s});
  80. 	while(pq.size()){
  81. 		auto [du, u] = pq.top(); pq.pop();
  82. 		if(-du > d[u]) continue;
  83. 		for(auto [v, w]: g[u]){
  84. 			ld wait = max(0, (int)(g[u].size()) - 2);
  85. 			if(d[v] > d[u] + 1.0 * w / V + wait){
  86. 				d[v] = d[u] + 1.0 * w / V + wait;
  87. 				pq.push({-d[v], v});
  88. 			}
  89. 		}
  90. 	}
  91. 	cout << fixed << setprecision(6) << d[t];
  92. 	cerr << "TIME ELAPSED: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  93. 	return 0;
  94. }
  95.  
Success #stdin #stdout #stderr 0.01s 11472KB
comments (?)
stdin 
3 3 7
1 2 8
2 3 9
1 3 20
1 3
stdout 
2.428571
stderr 
TIME ELAPSED: 0.008842s.
https://ideone.com/Ng3dnG
tôi là người đẹp trai nhất thế giới
language:
C++14 (clang 8.0)
created:
7 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!