fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define SPED                                                                                                           \
  4.     ios_base::sync_with_stdio(false);                                                                                  \
  5.     cin.tie(0);                                                                                                        \
  6.     cout.tie(0);
  7.  
  8. #define endl "\n"
  9. #define fi first
  10. #define se second
  11. #define lint long long
  12. #define fami signed
  13. #define lore main
  14. #define freefire freopen
  15. #define Data tuple<lint, int, int>
  16.  
  17. const lint INF = 0x1f1f1f1f1f1f1f1f;
  18. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  19.  
  20. using namespace std;
  21.  
  22. int n, t, m;
  23. lint dist[200005], dp[2][200005];     // hmm có khi dp được tính bằng bfs
  24. vector<int> adj[200005], rev[200005]; // can rev adj k?
  25.  
  26. void reset()
  27. {
  28.     for (int i = 1; i <= n; i++)
  29.     {
  30.         adj[i].clear();
  31.         rev[i].clear();
  32.     }
  33. }
  34.  
  35. void bfs()
  36. {
  37.     fill(dist + 1, dist + 1 + n, INF);
  38.     dist[1] = 0;
  39.     queue<int> temp;
  40.     temp.emplace(1);
  41.     while (!temp.empty())
  42.     {
  43.         auto now = temp.front();
  44.         temp.pop();
  45.  
  46.         for (auto v : adj[now])
  47.         {
  48.             if (dist[v] > dist[now] + 1)
  49.             {
  50.                 dist[v] = dist[now] + 1;
  51.                 temp.emplace(v);
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. void dijkstra()
  58. {
  59.     priority_queue<Data, vector<Data>, greater<Data>> pq;
  60.     for (int i = 1; i <= n; i++)
  61.     {
  62.         dp[0][i] = dist[i];
  63.         pq.emplace(dist[i], 0, i);
  64.     }
  65.  
  66.     fill(dp[1] + 1, dp[1] + 1 + n, INF);
  67.  
  68.     while (!pq.empty())
  69.     {
  70.         auto [du, cnt, u] = pq.top();
  71.         pq.pop();
  72.         if (du > dp[cnt][u])
  73.             continue;
  74.  
  75.         for (auto v : rev[u]) // cạnh ngược
  76.         {
  77.             if (dist[v] < dist[u]) // loại 1
  78.             {
  79.                 if (dp[cnt][v] > dp[cnt][u])
  80.                 {
  81.                     dp[cnt][v] = dp[cnt][u];
  82.                     pq.emplace(dp[cnt][v], cnt, v);
  83.                 }
  84.             }
  85.             else // loại 2
  86.             {
  87.                 if (cnt == 0)
  88.                 {
  89.                     if (dp[cnt + 1][v] > min(dp[cnt][u], dist[v]))
  90.                     {
  91.                         dp[cnt + 1][v] = min(dp[cnt][u], dist[v]);
  92.                         pq.emplace(dp[cnt + 1][v], cnt + 1, v);
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.     }
  98. }
  99.  
  100. fami lore()
  101. {
  102.     SPED;
  103.     cin >> t;
  104.     while (t--)
  105.     {
  106.         cin >> n >> m;
  107.         for (int i = 1; i <= m; i++)
  108.         {
  109.             int l, r;
  110.             cin >> l >> r;
  111.             adj[l].emplace_back(r);
  112.             rev[r].emplace_back(l);
  113.         }
  114.  
  115.         // cout << endl;
  116.  
  117.         bfs();
  118.         dijkstra();
  119.  
  120.         // for (int i = 1; i <= n; i++)
  121.         //     cout << dist[i] << " ";
  122.         // cout << endl;
  123.  
  124.         for (int i = 1; i <= n; i++)
  125.             cout << min(dp[0][i], dp[1][i]) << " ";
  126.  
  127.         cout << endl;
  128.         reset();
  129.     }
  130. }
  131. // Let your soul wander where dreams are born.
Success #stdin #stdout 0.01s 14104KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/usX98n
language:
C++14 (gcc 8.3)
created:
9 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!