fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #define int long long
  3. #define f1(i, n) for(int i=1;i<=n;++i)
  4. #define f0(i, n) for(int i=0;i<n;i++)
  5. #define all(x) x.begin(), x.end()
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define endl "\n"
  10. #define NAME "DUONGSAT"
  11. using namespace std;
  12.  
  13. const int MAXN = 1e5 + 5;
  14. const int INF = 2e9;
  15. const int abg = 1e3 + 5;
  16. const int base = 256;
  17.  
  18. int n, m, k;
  19. vector<int> g[5001];
  20. int dist[5001][5001][2];
  21.  
  22.  
  23. void bfs(int start) {
  24.     for (int i = 1; i <= n; ++i) {
  25.         dist[start][i][0] = INF;
  26.         dist[start][i][1] = INF;
  27.     }
  28.  
  29.     queue<pair<int, int>> pq;
  30.     pq.push({start, 0});
  31.     dist[start][start][0] = 0;
  32.     while (!pq.empty()) {
  33.         auto x = pq.front();
  34.         int u = x.first;
  35.         int mod = x.second;
  36.         pq.pop();
  37.         for (auto v : g[u]) {
  38.             int next_mod = 1 - mod;
  39.             if (dist[start][v][next_mod] == INF) {
  40.                 dist[start][v][next_mod] = dist[start][u][mod] + 1;
  41.                 pq.push({v, next_mod});
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47. int32_t main() {
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.     cout.tie(nullptr);
  51.  
  52.     if (fopen(NAME".INP", "r")) {
  53.         freopen(NAME".INP", "r", stdin);
  54.         freopen(NAME".OUT", "w", stdout);
  55.     }
  56.  
  57.     cin >> n >> m >> k;
  58.     for (int i = 1; i <= m; ++i) {
  59.         int u, v;
  60.         cin >> u >> v;
  61.         g[u].push_back(v);
  62.         g[v].push_back(u);
  63.     }
  64.  
  65.     for (int i = 1; i <= n; ++i) {
  66.         bfs(i);
  67.     }
  68.  
  69.     for (int i = 1; i <= k; ++i) {
  70.         int u, v, w;
  71.         cin >> u >> v >> w;
  72.         if (g[u].empty()) {
  73.             cout << "NO" << endl;
  74.             continue;
  75.         }
  76.         int wmod2 = w % 2;
  77.         int d = dist[u][v][wmod2];
  78.         if (d <= w) {
  79.             cout << "YES" << endl;
  80.         }
  81.         else cout << "NO" << endl;
  82.     }
  83.  
  84.  
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GcrH9g
language:
C++14 (gcc 8.3)
created:
3 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!