fork(1) download
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30. #define SZ(S) ((int) ((S).size()))
  31.  
  32. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  33. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  34. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  35.  
  36. const int INF = 1000000000;
  37.  
  38. struct Edge {
  39. int a, b, cap, flow;
  40. };
  41.  
  42. struct MaxFlow {
  43. int n, s, t;
  44. vector<int> d, ptr, q;
  45. vector< Edge > e;
  46. vector< vector<int> > g;
  47.  
  48. MaxFlow(int n) : n(n), d(n), ptr(n), g(n), q(n) {
  49. e.clear();
  50. REP(i,n) {
  51. g[i].clear();
  52. ptr[i] = 0;
  53. }
  54. }
  55.  
  56. void addEdge(int a, int b, int cap) {
  57. Edge e1 = { a, b, cap, 0 };
  58. Edge e2 = { b, a, 0, 0 };
  59. g[a].push_back( (int) e.size() );
  60. e.push_back(e1);
  61. g[b].push_back( (int) e.size() );
  62. e.push_back(e2);
  63. }
  64. int getMaxFlow(int _s, int _t) {
  65. s = _s; t = _t;
  66. int flow = 0;
  67. for (;;) {
  68. if (!bfs()) break;
  69. REP(i,n) ptr[i] = 0;
  70. while (int pushed = dfs(s, INF))
  71. flow += pushed;
  72. }
  73. return flow;
  74. }
  75.  
  76. private:
  77. bool bfs() {
  78. int qh = 0, qt = 0;
  79. q[qt++] = s;
  80. REP(i,n) d[i] = -1;
  81. d[s] = 0;
  82.  
  83. while (qh < qt && d[t] == -1) {
  84. int v = q[qh++];
  85. REP(i,g[v].size()) {
  86. int id = g[v][i], to = e[id].b;
  87. if (d[to] == -1 && e[id].flow < e[id].cap) {
  88. q[qt++] = to;
  89. d[to] = d[v] + 1;
  90. }
  91. }
  92. }
  93. return d[t] != -1;
  94. }
  95.  
  96. int dfs (int v, int flow) {
  97. if (!flow) return 0;
  98. if (v == t) return flow;
  99. for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
  100. int id = g[v][ptr[v]],
  101. to = e[id].b;
  102. if (d[to] != d[v] + 1) continue;
  103. int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
  104. if (pushed) {
  105. e[id].flow += pushed;
  106. e[id^1].flow -= pushed;
  107. return pushed;
  108. }
  109. }
  110. return 0;
  111. }
  112. };
  113.  
  114. const int MN = 111;
  115. const int MM = 10111;
  116. const int oo = 1000111000;
  117. int n, m, c[MN][MN];
  118. int eu[MM], ev[MM], ec[MM];
  119.  
  120. int main() {
  121. ios :: sync_with_stdio(false); cin.tie(NULL);
  122. cout << (fixed) << setprecision(6);
  123. while (cin >> n >> m) {
  124. FOR(i,1,n) FOR(j,1,n) c[i][j] = oo;
  125. FOR(i,1,n) c[i][i] = 0;
  126. FOR(i,1,m) {
  127. int u, v, l; cin >> u >> v >> l;
  128. ++u; ++v;
  129. eu[i] = u; ev[i] = v; ec[i] = l;
  130. c[u][v] = min(c[u][v], l);
  131. c[v][u] = c[u][v];
  132. }
  133. FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
  134.  
  135. if (c[1][n] == oo) {
  136. cout << 0 << endl;
  137. continue;
  138. }
  139.  
  140. MaxFlow flow(2*n);
  141. FOR(i,1,n) {
  142. int c = (i == 1 || i == n) ? oo : 1;
  143. flow.addEdge(2*i-2, 2*i-1, c);
  144. }
  145. FOR(i,1,m) {
  146. if (c[1][eu[i]] + ec[i] + c[ev[i]][n] == c[1][n])
  147. flow.addEdge(2*eu[i]-1, 2*ev[i]-2, oo);
  148. if (c[1][ev[i]] + ec[i] + c[eu[i]][n] == c[1][n])
  149. flow.addEdge(2*ev[i]-1, 2*eu[i]-2, oo);
  150. }
  151. int res = flow.getMaxFlow(0, 2*n-1);
  152. if (res >= oo) cout << "IMPOSSIBLE" << endl;
  153. else cout << res << endl;
  154. }
  155. return 0;
  156. }
  157.  
  158.  
Success #stdin #stdout 0s 3648KB
stdin
3 3
0 1 1
1 2 1
0 2 3
stdout
1