fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 2e5 + 5;
  38. int n, m;
  39. vector<ii> G[N], adj[N];
  40. int num[N], low[N], timer, dist[2][N];
  41. int bridge;
  42. stack<int> st;
  43.  
  44. void dfs(int u, int id) {
  45.     num[u] = low[u] = ++timer;
  46.     st.push(u);
  47.     for(ii x : adj[u]) {
  48.         int v, i; tie(v, i) = x;
  49.         if (i == id) continue;
  50.         if (num[v]) minimize(low[u], num[v]);
  51.         else {
  52.             dfs(v, i);
  53.             minimize(low[u], low[v]);
  54.             if (low[v] == num[v]) bridge++;
  55.         }
  56.     }
  57. }
  58.  
  59. void dijkstra(int src, int dist[]) {
  60.     priority_queue<ii, vector<ii>, greater<ii>> Q;
  61.     FOR(i, 1, n) dist[i] = inf;
  62.     dist[src] = 0;
  63.     Q.push(mp(0, src));
  64.     while(!Q.empty()) {
  65.         int du, u; tie(du, u) = Q.top(); Q.pop();
  66.         if (du != dist[u]) continue;
  67.         for(ii x : G[u]) {
  68.             int v, w; tie(v, w) = x;
  69.             if (minimize(dist[v], dist[u] + w))
  70.                 Q.push(mp(dist[v], v));
  71.         }
  72.     }
  73. }
  74.  
  75. void init(void) {
  76.     cin >> n >> m;
  77.     FOR(i, 1, m) {
  78.         int u, v, w;
  79.         cin >> u >> v >> w;
  80.         G[u].pb(mp(v, w));
  81.         G[v].pb(mp(u, w));
  82.     }
  83. }
  84.  
  85. void process(void) {
  86.     dijkstra(1, dist[0]);
  87.     dijkstra(n, dist[1]);
  88.     auto check = [&](int mid) {
  89.         FOR(i, 1, n) {
  90.             num[i] = low[i] = 0;
  91.             adj[i].clear();
  92.         }
  93.         st = stack<int>();
  94.         timer = bridge = 0;
  95.  
  96.         int id = 0;
  97.         FOR(i, 1, n) for(ii x : G[i]) {
  98.             int v, w; tie(v, w) = x;
  99.             if (dist[0][i] + w + dist[1][v] <= mid) {
  100.                 adj[i].pb(mp(v, id));
  101.                 adj[v].pb(mp(i, id));
  102.                 id++;
  103.             }
  104.         }
  105.  
  106.         FOR(i, 1, n) if (!num[i])
  107.             dfs(i, -1);
  108.  
  109.         return bridge;
  110.     };
  111.  
  112.     int low = dist[0][n], high = 1e9, res = 0;
  113.     while(low <= high) {
  114.         int mid = (low + high) >> 1;
  115.         if (check(mid) == 0) res = mid, high = mid - 1;
  116.         else low = mid + 1;
  117.     }
  118.     cout << res << ' ' << check(res - 1) << '\n';
  119. }
  120.  
  121. int main() {
  122.     ios_base::sync_with_stdio(0);
  123.     cin.tie(0); cout.tie(0);
  124.     if (fopen(task".inp", "r")) {
  125.         freopen(task".inp", "r", stdin);
  126.         freopen(task".out", "w", stdout);
  127.     }
  128.     int tc = 1;
  129. //    cin >> tc;
  130.     while(tc--) {
  131.         init();
  132.         process();
  133.     }
  134.     return 0;
  135. }
  136.  
  137.  
Success #stdin #stdout 0.01s 14228KB
comments (?)
stdin 
Standard input is empty
stdout 
0 0
https://ideone.com/KgnjVZ
language:
C++14 (gcc 8.3)
created:
2 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!