Submission #35205404

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>;

vector<pair<int,ll> > g[200010]; // g[u] = {v,w};
int fa[200010]; // DSU
int find(int v){return v==fa[v]?v:(fa[v]=find(fa[v]));}
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main() {
  int n = read();
  int m = read();
  int k = read();

  vector<tuple<ll,int,int> > e; // w,u,v 原图的边
  rep(i,0,m){
    int u = read()-1; // 0-index
    int v = read()-1;
    ll w = read();
    e.push_back({w,u,v});
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  vector<ll> h(n);     // 最近休息点
  vector<ll> d(n,INF); // 到最近休息点的距离
  minPQ<tuple<ll,int,int> > pq; // {dis, u, 休息点}
  rep(i,0,k) pq.push({0,i,i});
  for(int cnt = n;!pq.empty() && cnt > 0;) {
    auto [c,u,x] = pq.top();
    pq.pop();
    if (d[u]!=INF) continue;
    d[u] = c;
    h[u] = x;
    cnt --;
    for(auto [v,w]:g[u])if(d[v]==INF)pq.push({c+w,v,x});
  }

  vector<tuple<ll,int,int> > e2; // w u v, 只有k个点的图的边
  for(auto [w,u,v]:e) if(h[u] != h[v]) e2.push_back({d[u]+d[v]+w,h[u], h[v]}); // h[u]..u..v..h[v]
  sort(e2.begin(), e2.end());
  iota(fa,fa+k,0);

  int q = read();
  int i = 0;
  while(q--){
    int x = read()-1;
    int y = read()-1;
    ll t = read();
    while(i<(int)e2.size()){
      auto [w,u,v] = e2[i];
      if(w > t)break;
      fa[find(u)] = find(v);
      i++;
    }
    printf("%s\n",find(x)==find(y) ? "Yes" : "No");
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:5:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result