mr_dot_convict

1416-Warfare-And-Logistics-UVa-mr.convict

May 15th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.22 KB | None | 0 0
  1. /*author* Priyanshu Shrivastav (from IIT Palakkad) *
  2.  * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
  3.  * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
  4.  * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
  5.  * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
  6. When I wrote this, only God and I understood what I was doing
  7.  ** * * * * * * * Now, only God knows * * * * * * */
  8. #include         <bits/stdc++.h>
  9. #pragma GCC      optimize ("Ofast")
  10. #pragma GCC      optimize ("unroll-loops")
  11. #pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  12.  
  13. #define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
  14. #define PREC     cout.precision (10); cout << fixed
  15. #define x        first
  16. #define y        second
  17. using namespace std;
  18. using pii = pair <int, int>;
  19.  
  20. const int infi = (int)1e9;
  21. const int N = 105;
  22. const int M = 2010;
  23.  
  24. struct edge {
  25.    int v, w, id;
  26.    inline bool operator > (const edge& oth) const {
  27.       return w > oth.w;
  28.    }
  29. };
  30.  
  31. int n, m, L;
  32. vector < vector <edge> > Adj;
  33. long long damage[M], actualCost; //damage[k] = sum(d[i][j]) when edge with idx = k is removed
  34. int dist[N], Par[N];
  35.  
  36. void dijkstra(int src, int banIdx, int d[], int Pi[]) {
  37.    bool vis[N];
  38.    for (int i = 0; i < n; ++i)
  39.       vis[i] = false, d[i] = infi, Pi[i] = -1;
  40.  
  41.    d[src] = 0;
  42.    priority_queue <pii, vector <pii>, greater <pii> > Q;
  43.    Q.push(pii(d[src], src));
  44.  
  45.    while (!Q.empty()) {
  46.       pii tmp = Q.top();
  47.       Q.pop();
  48.       int u = tmp.y;
  49.       if (vis[u]) continue;
  50.       vis[u] = true;
  51.  
  52.       for (edge E : Adj[u]) {
  53.          int v = E.v, w = E.w, id = E.id;
  54.          if (banIdx == id) continue;
  55.  
  56.          if (!vis[v] && d[u] < infi && d[v] > d[u] + w) {
  57.             d[v] = d[u] + w;
  58.             Pi[v] = id;
  59.             Q.push(pii(d[v], v));
  60.          }
  61.       }
  62.    }
  63.  
  64. }
  65.  
  66. void solve() {
  67.    for (int i = 0; i < m; ++i)
  68.       damage[i] = 0;
  69.  
  70.    actualCost = 0;
  71.    for (int i = 0; i < n; ++i) {
  72.  
  73.       dijkstra(i, -1, dist, Par);
  74.  
  75.       long long sumOverj = 0;
  76.       for (int j = 0; j < n; ++j) {
  77.          sumOverj += (dist[j] == infi ? L : dist[j]);
  78.       }
  79.       actualCost += sumOverj;
  80.  
  81.       bool inSpanTree[M];
  82.       for (int k = 0; k < m; ++k)
  83.          inSpanTree[k] = false;
  84.  
  85.       for (int j = 0; j < n; ++j)
  86.          if (j != i) inSpanTree[Par[j]] = true;
  87.  
  88.       for (int k = 0; k < m; ++k) { // correction
  89.          if (inSpanTree[k]) { // will run atmost n - 1 time
  90.             dijkstra(i, k, dist, Par);
  91.  
  92.             long long sumOverjWOk = 0;
  93.             for (int j = 0; j < n; ++j)
  94.                sumOverjWOk += (dist[j] == infi ? L : dist[j]);
  95.             damage[k] += sumOverjWOk;
  96.          }
  97.          else damage[k] += sumOverj;
  98.       }
  99.    }
  100.  
  101.    long long mx = actualCost;
  102.    for (int i = 0; i < m; ++i) {
  103.       mx = max(mx, damage[i]);
  104.    }
  105.  
  106.    cout << actualCost << ' ' << mx << '\n';
  107. }
  108.  
  109. void read() {
  110.    Adj.assign(n, vector <edge> ());
  111.  
  112.    int u, v, c;
  113.    for (int i = 0; i < m; ++i) {
  114.       cin >> u >> v >> c;
  115.       --u, --v;
  116.       Adj[u].push_back({v, c, i});
  117.       Adj[v].push_back({u, c, i});
  118.    }
  119. }
  120.  
  121. signed main() {
  122.    while (cin >> n >> m >> L) {
  123.       read();
  124.       solve();
  125.    }
  126.  
  127.    return EXIT_SUCCESS;
  128. }
Add Comment
Please, Sign In to add comment