fork download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8.  
  9. #include<stack>
  10. #include<bitset>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <cstring>
  17. #include <cctype>
  18. #include <cassert>
  19. #include <limits>
  20. #include <functional>
  21. #include<unordered_map>
  22.  
  23. #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  24.  
  25. #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
  26. #define aut(r,v) for(auto r:v)
  27.  
  28. #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
  29. #define all(o) (o).begin(), (o).end()
  30. #define pb(x) push_back(x)
  31. #define pc()  pop_back()
  32.  
  33. #define ull unsigned long long
  34. #define mp(x,y) make_pair((x),(y))
  35. #define mset(m,v) memset(m,v,sizeof(m))
  36.  
  37. #define INF 0x3f3f3f3f
  38. #define INFL 0x3f3f3f3f3f3f3f3fLL
  39. using namespace std;
  40. #define endl '\n'
  41.  
  42. #define st stack<int>
  43.  
  44.  
  45.  
  46. #define vl vector<long long>
  47. #define vi vector<int>
  48. #define vb vector<bool>
  49. #define vc vector<char>
  50. #define pii pair<int,int>
  51. #define vpii vector<pii>
  52. #define vvi vector<vi>
  53. #define vs vector<string>
  54.  
  55. #define mod 1000000007
  56.  
  57. #define un  unordered_map<int,int>
  58. #define mii map<int,int>
  59.  
  60. #define Sort(a) sort(all(a))
  61. #define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
  62.  
  63. #define max3(a, b, c)   max(a, max(b, c))
  64. #define min3(a, b, c)   min(a, min(b, c))
  65. #define Max(a)       *max_element(all(a))
  66. #define Min(a)       *min_element(all(a))
  67. #define MaxP(a)       max_element(all(a)) - a.begin()
  68. #define MinP(a)        min_element(all(a)) - a.begin()
  69.  
  70. #define allUpper(a)     transform(all(a), a.begin(), :: toupper)
  71. #define allLower(a)     transform(all(a), a.begin(), :: tolower)
  72.  
  73. #define rev(a)          reverse(all(a))
  74. #define ub(v,k)          upper_bound(all(v), k) - v.begin()
  75. #define lb(v,k)          lower_bound(all(v), k) - v.begin()
  76. #define adv(a,n)        advance(auto it:a,n)
  77. #define RSort(a)         sort(a.rbegin(),a.rend()) //decending order
  78. #define cnt(v,a)             count(all(v),a)
  79. #define bs(v,a)           binary_search(all(v),a)
  80. #define mmax(v)           *max_element(all(v))
  81. #define mmin(v)           *min_element(all(v))
  82. #define popcount(mask)                       __builtin_popcount(mask) // count set bit
  83. #define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
  84. #define X real() // useful for working with #include <complex> for computational geometry
  85. #define Y imag()
  86. #define ll long long
  87. #define ss second
  88. #define ff first
  89.  
  90. #define trace1(x)                           cerr << #x << ": " << x << endl;
  91. #define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  92. #define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  93. #define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  94. #define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  95. #define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  96.  
  97. //------------------------------CODE-----------------------------------------------------------------------
  98. void bfs(int source, vvi& adj, vi& ans) {
  99.     vi vis(ans.size(), false);
  100.     vis[source] = true;
  101.     ans[source] = 0;
  102.     queue<int>q;
  103.     q.push(source);
  104.     while (!q.empty()) {
  105.         int cur = q.front();
  106.         q.pop();
  107.         for (auto it : adj[cur]) {
  108.             if (!vis[it]) {
  109.                 q.push(it);
  110.                 vis[it] = true;
  111.                 ans[it] = ans[cur] + 1;
  112.             }
  113.         }
  114.     }
  115.  
  116. }
  117.  
  118.  
  119.  
  120. int main() {
  121.     ios_base::sync_with_stdio(false);
  122.     cin.tie(NULL);
  123.     cout.tie(NULL);
  124.     int test;
  125.     test = 1;
  126.     //cin >> test;
  127.     //preprocess();
  128.  
  129.     while (test--) {
  130.         int n;
  131.         cin >> n;
  132.         vvi v(n, vi(n));
  133.         rep(i, n) {
  134.             rep(j, n) {
  135.                 cin >> v[i][j];
  136.             }
  137.         }
  138.         vvi ans(n, vi(n, -1));
  139.         vvi adj(n );
  140.         rep(i, n) {
  141.             rep(j, n) {
  142.                 if (v[i][j] == 1) {
  143.                     adj[j].push_back(i);
  144.                 }
  145.             }
  146.         }
  147.         rep(i, n) {
  148.             bfs(i, adj, ans[i]);
  149.         }
  150.  
  151.         rep(i, n) {
  152.             if (v[i][i] == 1) {
  153.                 ans[i][i] = 1;
  154.  
  155.            }
  156.             else {
  157.                 ans[i][i] = INF;
  158.                 rep(j, n) {
  159.                     if (i == j)continue;
  160.                     else {
  161.                         if (ans[i][j] > 0 && ans[j][i] > 0) {
  162.                             ans[i][i] = min(ans[i][i], ans[i][j] + ans[j][i]);
  163.                         }
  164.                     }
  165.                 }
  166.             }
  167.         }
  168.         rep(i, n) {
  169.             if (ans[i][i] == INF)cout << "NO WAY" << endl;
  170.             else cout << ans[i][i] << endl;
  171.         }
  172.  
  173.     }
  174.  
  175.  
  176.  
  177.  
  178. };
Success #stdin #stdout 0s 4188KB
comments (?)
stdin
copy 
5
0 1 1 1 1
1 0 0 0 1
0 0 1 1 0
0 0 1 0 0
0 0 0 1 0
stdout
copy 
2
2
1
2
NO WAY
https://ideone.com/hPoxpD
language:
C++14 (gcc 8.3)
created:
3 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!