fork download 
  1. /*
  2.  * Author    : Apu Das Orgho
  3.  * Problem   : Series-Parallel Voltage Calculator
  4.  * Created on: 27-09-2025
  5.  */
  6. #include <bits/stdc++.h>
  7. #define iamspeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  8. #define endl '\n'
  9. using namespace std;
  10. using ll = long long;
  11. using ld = long double;
  12.  
  13. struct E {
  14.     int a, b;
  15.     ll w;
  16. };
  17.  
  18. int main() {
  19.     iamspeed
  20.     int n, m;
  21.     ll V;
  22.     if (!(cin >> n >> m >> V)) return 0;
  23.     vector<E> edges(m);
  24.     vector<vector<pair<int, int> > > adj(n);
  25.     for (int i = 0; i < m; i++) {
  26.         int a, b;
  27.         ll c;
  28.         cin >> a >> b >> c;
  29.         edges[i] = {a, b, c};
  30.         adj[a].push_back({b, i});
  31.         adj[b].push_back({a, i});
  32.     }
  33.     int q;
  34.     cin >> q;
  35.     if (q == 0) {
  36.         cout.setf(std::ios::fixed);
  37.         cout << setprecision(10) << (ld) V << "\n";
  38.         return 0;
  39.     }
  40.     if (q == n - 1) {
  41.         cout.setf(std::ios::fixed);
  42.         cout << setprecision(10) << 0.0L << "\n";
  43.         return 0;
  44.     }
  45.  
  46.     vector<int> deg(n);
  47.     for (int i = 0; i < n; i++) deg[i] = adj[i].size();
  48.     vector<char> isJ(n, 0);
  49.     for (int i = 0; i < n; i++) if (i == 0 || i == n - 1 || deg[i] != 2) isJ[i] = 1;
  50.  
  51.     vector<char> used(m, 0);
  52.     unordered_map<unsigned long long, ld> invsum;
  53.     invsum.reserve(m * 2);
  54.     bool qJ = isJ[q];
  55.     int qs = -1, qt = -1;
  56.     ld qd = 0.0L, qL = 0.0L;
  57.  
  58.     for (int u = 0; u < n; u++)
  59.         if (isJ[u]) {
  60.             for (auto [v,eid]: adj[u]) {
  61.                 if (used[eid]) continue;
  62.                 int cur = v, pe = eid;
  63.                 ld L = edges[eid].w;
  64.                 used[eid] = 1;
  65.                 if (!qJ && cur == q && qs == -1) {
  66.                     qs = u;
  67.                     qd = L;
  68.                 }
  69.                 while (!isJ[cur]) {
  70.                     int ne = -1, nx = -1;
  71.                     for (auto [nb,id]: adj[cur])
  72.                         if (id != pe) {
  73.                             ne = id;
  74.                             nx = nb;
  75.                             break;
  76.                         }
  77.                     if (ne == -1) break;
  78.                     L += edges[ne].w;
  79.                     used[ne] = 1;
  80.                     if (!qJ && nx == q && qs == -1) {
  81.                         qs = u;
  82.                         qd = L;
  83.                     }
  84.                     pe = ne;
  85.                     cur = nx;
  86.                 }
  87.                 int a = u, b = cur;
  88.                 if (a > b) swap(a, b);
  89.                 unsigned long long key = ((unsigned long long) a << 32) | (unsigned int) b;
  90.                 invsum[key] += 1.0L / L;
  91.                 if (qs == u && qt == -1) {
  92.                     qt = cur;
  93.                     qL = L;
  94.                 }
  95.             }
  96.         }
  97.  
  98.     vector<vector<pair<int, ld> > > G(n);
  99.     G.reserve(n);
  100.     for (auto &kv: invsum) {
  101.         unsigned long long key = kv.first;
  102.         ld Req = 1.0L / kv.second;
  103.         int a = (int) (key >> 32), b = (int) (key & 0xffffffffu);
  104.         G[a].push_back({b, Req});
  105.         G[b].push_back({a, Req});
  106.     }
  107.  
  108.     vector<int> nodes;
  109.     vector<ld> er;
  110.     int prev = -1, cur = 0;
  111.     nodes.push_back(0);
  112.     while (cur != n - 1) {
  113.         auto &nbr = G[cur];
  114.         int nxt = -1;
  115.         ld R = 0;
  116.         for (auto [x,r]: nbr)
  117.             if (x != prev) {
  118.                 nxt = x;
  119.                 R = r;
  120.                 break;
  121.             }
  122.         if (nxt == -1) {
  123.             nxt = nbr[0].first;
  124.             R = nbr[0].second;
  125.         }
  126.         er.push_back(R);
  127.         nodes.push_back(nxt);
  128.         prev = cur;
  129.         cur = nxt;
  130.     }
  131.  
  132.     int k = nodes.size();
  133.     vector<ld> pref(k, 0.0L);
  134.     for (int i = 1; i < k; i++) pref[i] = pref[i - 1] + er[i - 1];
  135.     ld Rtot = pref.back();
  136.  
  137.     ld RtoQ = 0.0L;
  138.     if (isJ[q]) {
  139.         int idx = -1;
  140.         for (int i = 0; i < k; i++)
  141.             if (nodes[i] == q) {
  142.                 idx = i;
  143.                 break;
  144.             }
  145.         RtoQ = pref[idx];
  146.     } else {
  147.         int is = -1, it = -1;
  148.         for (int i = 0; i < k; i++) {
  149.             if (nodes[i] == qs) is = i;
  150.             if (nodes[i] == qt) it = i;
  151.         }
  152.         if (is < it) RtoQ = pref[is] + qd;
  153.         else RtoQ = pref[it] + (qL - qd);
  154.     }
  155.  
  156.     ld I = (ld) V / Rtot;
  157.     ld Vq = (ld) V - I * RtoQ;
  158.     cout.setf(std::ios::fixed);
  159.     cout << setprecision(10) << (double) Vq << "\n";
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/IPWBA7
language:
C++14 (gcc 8.3)
created:
4 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!