#include using namespace std; const int MX = 1e5+2; vector> adj[MX]; int qry[MX], ans[MX]; map dist2ind; struct foo { int u, w; bool operator<(const foo& f) const { return w > f.w; } }; void dijkstra(int src, vector& dist) { priority_queue pq; pq.push({src, 0}); dist[src] = 0; while(pq.size()) { int u = pq.top().u, w = pq.top().w; pq.pop(); if(w != dist[u]) continue; for(auto e: adj[u]) { if(dist[e.first] > w+e.second ) { dist[e.first] = w+e.second; pq.push({e.first, dist[e.first]}); } } } } struct segtree { vector seg; int n; segtree(int _n) { n = _n; seg.resize(2*n, INT_MAX); } void upd(int i, int v) { i += n; seg[i] = min(seg[i], v); while(i /= 2) seg[i] = min(seg[i*2], seg[i*2+1]); } int qry(int l, int r) { l += n, r += n; int ret = INT_MAX; while(l < r) { if(l&1) ret = min(ret, seg[l++]); if(r&1) ret = min(ret, seg[--r]); l /= 2, r /= 2; } return ret; } }; int32_t main() { ios::sync_with_stdio(0);cin.tie(0); int n, a, b, c, m; cin >> n >> a >> b >> c >> m; vector da(n+1, INT_MAX), db(n+1, INT_MAX), dc(n+1, INT_MAX); while(m--) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } memset(qry, -1, sizeof qry); dijkstra(a, da); dijkstra(b, db); dijkstra(c, dc); vector v(n); for(int i=0; i= dc[t]; //printf("for node %d: qried[0, %d]=%d, dc=%d\n", t, dist2ind[db[t]], qried, dc[t]); } for(int k=i; k> q; for(int i=0; i> t; cout << (ans[t] ? "YES\n" : "NO\n"); } }

코드 #3041