fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty