fork download
copy 
  1. //
  2. // Created by Dmitry Gorbunov on 05/08/2017.
  3. //
  4.  
  5. //
  6. // Created by Dmitry Gorbunov on 01/08/2017.
  7. //
  8.  
  9. #include <iostream>
  10. #include <fstream>
  11. #include <sstream>
  12.  
  13. #include <vector>
  14. #include <set>
  15. #include <bitset>
  16. #include <map>
  17. #include <deque>
  18. #include <string>
  19.  
  20. #include <algorithm>
  21. #include <numeric>
  22.  
  23. #include <cstdio>
  24. #include <cassert>
  25. #include <cstdlib>
  26. #include <cstring>
  27. #include <ctime>
  28. #include <cmath>
  29.  
  30. #define pb push_back
  31. #define pbk pop_back
  32. #define mp make_pair
  33. #define fs first
  34. #define sc second
  35. #define all(x) (x).begin(), (x).end()
  36. #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
  37. #define len(a) ((int) (a).size())
  38.  
  39. #ifdef CUTEBMAING
  40. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  41. #else
  42. #define eprintf(...) 42
  43. #endif
  44.  
  45. using namespace std;
  46.  
  47. typedef long long int64;
  48. typedef long double ld;
  49. typedef unsigned long long lint;
  50.  
  51. const int inf = (1 << 30) - 1;
  52. const int64 linf = (1ll << 62) - 1;
  53. const int N = static_cast<int>(1e5 + 100);
  54. const int MAX_INCREASE = static_cast<int>(1e6 + 100);
  55. const int s = 0;
  56.  
  57. int n, m, q;
  58. int a[N], b[N], c[N];
  59.  
  60. namespace graph {
  61. int first[N], next[N], from[N], to[N], cost[N], w[N];
  62.  
  63. inline void clear() {
  64.   fill_n(first, n, -1);
  65.   fill_n(next, n, -1);
  66. }
  67.  
  68. inline void addEdge(int i, int u, int v, int c) {
  69.   graph::from[i] = u, graph::to[i] = v, graph::cost[i] = c;
  70.   graph::next[i] = graph::first[u];
  71.   graph::first[u] = i;
  72. }
  73. }
  74.  
  75. int64 dist[N];
  76. bool used[N];
  77.  
  78. void initialDijkstra() {
  79.   fill_n(dist, n, linf);
  80.   dist[s] = 0;
  81.   set<pair<int, int>> q = { { dist[s], s } };
  82.   while (!q.empty()) {
  83.     int v = q.begin()->second;
  84.     q.erase(q.begin());
  85.     used[v] = true;
  86.     for (int edge = graph::first[v]; edge != -1; edge = graph::next[edge]) {
  87.       int to = graph::to[edge], cost = graph::cost[edge];
  88.       if (dist[to] > dist[v] + cost) {
  89.         q.erase(make_pair(dist[to], to));
  90.         dist[to] = dist[v] + cost;
  91.         q.insert(make_pair(dist[to], to));
  92.       }
  93.     }
  94.   }
  95. }
  96.  
  97. int total = 0;
  98.  
  99. namespace queue {
  100. int first[MAX_INCREASE], vertex[N], next[N], cc = 0;
  101.  
  102. inline void clear() {
  103.   fill_n(first, total, -1);
  104.   cc = 0;
  105. }
  106.  
  107. inline void addToQueue(int dist, int vertex) {
  108.   queue::vertex[cc] = vertex;
  109.   queue::next[cc] = queue::first[dist];
  110.   queue::first[dist] = cc++;
  111. }
  112. }
  113.  
  114. void recalc() {
  115.   queue::clear();
  116.   for (int i = 0; i < m; i++) {
  117.     if (graph::cost[i] + dist[graph::from[i]] - dist[graph::to[i]] > total) {
  118.       graph::w[i] = inf;
  119.     } else {
  120.       graph::w[i] = static_cast<int>(graph::cost[i] + dist[graph::from[i]] - dist[graph::to[i]]);
  121.     }
  122.   }
  123.   static int potentialDist[N];
  124.   fill_n(potentialDist, n, inf);
  125.   potentialDist[s] = 0;
  126.   queue::addToQueue(potentialDist[s], s);
  127.   for (int i = 0; i <= total; i++) {
  128.     while (queue::first[i] != -1) {
  129.       int start = queue::first[i];
  130.       queue::first[i] = -1;
  131.       for (int index = start; index != -1; index = queue::next[index]) {
  132.         int v = queue::vertex[index];
  133.         if (potentialDist[v] != i) {
  134.           continue;
  135.         }
  136.         for (int edge = graph::first[v]; edge != -1; edge = graph::next[edge]) {
  137.           int to = graph::to[edge], cost = graph::w[edge];
  138.           int newDistance = potentialDist[v] + cost;
  139.           if (newDistance <= total && potentialDist[to] > newDistance) {
  140.             potentialDist[to] = newDistance;
  141.             queue::addToQueue(potentialDist[to], to);
  142.           }
  143.         }
  144.       }
  145.     }
  146.   }
  147.   for (int i = 0; i < n; i++) {
  148.     dist[i] += potentialDist[i];
  149.   }
  150.   total = 0;
  151. }
  152.  
  153. int main() {
  154.   cin >> n >> m >> q;
  155.   graph::clear();
  156.   for (int i = 0; i < m; i++) {
  157.     int u, v, c; scanf("%d%d%d", &u, &v, &c), u--, v--;
  158.     graph::addEdge(i, u, v, c);
  159.   }
  160.   initialDijkstra();
  161.   for (int i = 0; i < q; i++) {
  162.     int t; scanf("%d", &t);
  163.     if (t == 1) {
  164.       int v; scanf("%d", &v); v--;
  165.       if (total > 0) {
  166.         recalc();
  167.       }
  168.       if (used[v]) {
  169.         printf("%lld\n", dist[v]);
  170.       } else {
  171.         printf("-1\n");
  172.       }
  173.     } else if (t == 2) {
  174.       int c; scanf("%d", &c);
  175.       for (int j = 0; j < c; j++) {
  176.         int edge; scanf("%d", &edge); edge--;
  177.         ++graph::cost[edge];
  178.       }
  179.       total += c;
  180.     } else {
  181.       assert(false);
  182.     }
  183.   }
  184.   return 0;
  185. }
Time limit exceeded #stdin #stdout 5s 25544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KnxwBY
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!