fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int n, m;
  8.     long double T;
  9.     if(!(cin >> n >> m >> T)) return 0;
  10.  
  11.     vector<vector<pair<int,long double>>> g(n+1);
  12.     for (int i = 0; i < m; ++i) {
  13.         int u, v;
  14.         long double l, c;
  15.         cin >> u >> v >> l >> c;
  16.         long double w = sqrtl(l * c);          // trọng số w = sqrt(l*c)
  17.         g[u].push_back({v, w});
  18.         g[v].push_back({u, w});
  19.     }
  20.  
  21.     const long double INF = 1e100L;
  22.     vector<long double> dist(n+1, INF);
  23.     priority_queue<pair<long double,int>,
  24.                    vector<pair<long double,int>>,
  25.                    greater<pair<long double,int>>> pq;
  26.  
  27.     dist[1] = 0;
  28.     pq.push({0,1});
  29.     while(!pq.empty()){
  30.         auto [d,u] = pq.top(); pq.pop();
  31.         if(d != dist[u]) continue;
  32.         if(u == n) break;
  33.         for(auto [v,w] : g[u]){
  34.             if(dist[v] > d + w){
  35.                 dist[v] = d + w;
  36.                 pq.push({dist[v], v});
  37.             }
  38.         }
  39.     }
  40.  
  41.     long double S = dist[n];
  42.     long double ans = (S*S) / T;               // (sum w)^2 / T
  43.     cout.setf(std::ios::fixed); 
  44.     cout << setprecision(10) << ans << "\n";
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
4 5 9
1 2 6 7
1 3 6 2
2 3 8 7
2 4 3 4
3 4 1 7
stdout 
4.1478114200
https://ideone.com/8pFUy3
language:
C++14 (gcc 8.3)
created:
13 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!