AOJ0275.cc

AOJ0275.cc

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define sz(v) ((int)(v).size())
#define repsz(i, v) rep(i, sz(v))
#define eb emplace_back
#define pb push_back
#define mt make_tuple
#define mp make_pair
#define cauto const auto &
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define bit(i) (1LL<<(i))
using namespace std;

// n 頂点, m 辺, q クエリ, d(s, t) = L の時,
// Bビット並列で 1/B くらいの回数にするので,
// 気持ち的には, O(n + m + q + L + (n + m) q / B * B).
// n <= 1E5, m <= 2E5, l <= 1E3 (i.e. L <= 1E8).
// (n+m) q の n の部分とか落とせるけど, もういいやという気になった.

const int B = 256;
typedef bitset<B> BIT;

const int N = 110000;
const int M = 440000;

struct E{ int to; int cost; E *next; };
E _edges[M];
E *g[N];

inline void init(const int &n){ rep(i, n) g[i] = 0; }
inline void add(const int &s, const int &t, const int &c){
    static int i = 0;
    _edges[i].to = t; _edges[i].cost = c;
    _edges[i].next = g[s]; g[s] = _edges+i++;
}
#define each_edge(e, v) for(E *e = g[v]; e; e = e->next)

BIT bits[N];
int d[N];
int Q[N];
int flg[N] = {};
int _order[N];
pair<int, int> es[M];
pair<int, int> query[41000];
int main(){
    int n, m; scanf("%d %d", &n, &m);
    init(n);
    rep(i, m){
        int u, v, c; scanf("%d %d %d", &u, &v, &c); --u; --v;
        add(u, v, c); add(v, u, c);
    }
    int s, t, q; scanf("%d %d %d", &s, &t, &q); --s; --t;
    rep(i, q){
        scanf("%d %d", &query[i].first, &query[i].second);
        --query[i].first; --query[i].second;
    }
    int nn = 0;
    { // O(m + L): dijkstra. use bucket (implement: ring buffer) insted of priority queue
        fill(d, d+n, 1<<30);
        vector<int> buf[1024];
        buf[d[s] = 0].eb(s);
        int cnt = 1;
        for(int c = 0; cnt && c <= d[t]; ++c){
            for(cauto u : buf[c&1023]){
                if(d[u] > c) continue;
                _order[nn++] = u; // topological order (\supset the objective DAG)
                each_edge(e, u){
                    const int nc = c + e->cost;
                    const int &v = e->to;
                    if(d[v] > nc) buf[ (d[v] = nc) & 1023 ].eb(v), ++cnt;
                }
            }
            cnt -= buf[c&1023].size();
            buf[c&1023].clear();
        }
    }
    int mm = 0;
    { // O(m): create "the" DAG. (store edges in reversed topological order)
        fill(flg, flg+n, 0); flg[t] = true;
        for(int i = nn-1; i >= 0; --i){
            const int &u = _order[i];
            if(flg[u]) each_edge(e, u){
                const int &v = e->to;
                if(d[v] + e->cost == d[u]){
                    flg[v] = true; es[mm++] = mp(u, v);
                }
            }
        }
    }

    { // O(mq / B * B): solve each query using bit parallel
        pair<int, int> *ptr = query;
        for(int geta = 0; geta < q; geta += B, ptr += B){
            const int t = min(q - geta, B);
            rep(i, n) bits[i].reset();
            rep(i, t) bits[ptr[i].second][i] = true;
            rep(i, mm) bits[es[i].second] |= bits[es[i].first];
            rep(i, t) puts(bits[ptr[i].first][i] ? "Yes" : "No");
        }
    }
    return 0;
}