AOJ 0275 - Railroad

問題文 : 鉄道路線

解放 :

Dijkstra して得られる最短経路からDAG を作成してクエリ毎にDP をすれば良い. しかしクエリごとに処理するときに(1ll << (j % 64)) を(1 << (j % 64)) と書いていて12 時間くらい悩んでいた... 本番ではこんなミス絶対しないように戒心.

クエリを並列処理することで$O(MQ)$ 時間の定数がめっちゃ軽い感じで解け8 sec 以内に余裕で間に合う. しかし本番ではDAGDP を少し改善するだけでも通ったらしい...w

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
struct Edge {
    int to, cost;
    Edge(int to, int cost) : to(to), cost(cost){}
    Edge(){}
};
 
bool operator < (const Edge &a, const Edge &b)
{
    return (a.cost > b.cost);
}
 
long long int accessable[100000];
bool vis[100000];
vector<Edge> TG[100000];
vector<int> G[100000];
int c[40000], d[40000];
vector<int> topo;
 
void dfs(int v)
{
    vis[v] = true;
     
    for (int i = 0; i < G[v].size(); i++)
        if (!vis[G[v][i]]) dfs(G[v][i]);
    topo.push_back(v);
}
 
int main()
{
    int N, M;
     
    scanf("%d %d", &N, &M);
     
    for (int i = 0; i < M; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        --u; --v;
        TG[u].push_back(Edge(v, w));
        TG[v].push_back(Edge(u, w));
    }
     
    int a, b, Q;
     
    scanf("%d %d %d", &a, &b, &Q);
     
    --a; --b;
     
    for (int i = 0; i < Q; i++){
        scanf("%d %d", c + i, d + i);
        --c[i]; --d[i];
    }
     
    priority_queue<Edge> pq;
    bool done[100000] = {0};
    int weight[100000];
    fill(weight, weight + N, 1001001001);
     
    for (pq.push(Edge(a, 0)); pq.size(); pq.pop()){
        Edge x = pq.top();
         
        if (done[x.to]) continue;
        done[x.to] = true;
        weight[x.to] = x.cost;
         
        for (int i = 0; i < TG[x.to].size(); i++){
            pq.push(Edge(TG[x.to][i].to, x.cost + TG[x.to][i].cost));
        }
    }
     
    int in[100000] = {0};
    queue<int> q;
    memset(done, 0, sizeof(done));
     
    for (q.push(b); q.size(); q.pop()){
        int x = q.front();
        if (done[x]) continue;
        for (int i = 0; i < TG[x].size(); i++){
            if (weight[x] == weight[TG[x][i].to] + TG[x][i].cost){
                q.push(TG[x][i].to);
                G[TG[x][i].to].push_back(x);
                in[x]++;
            }
        }
        done[x] = true;
    }
     
    for (int i = 0; i < N; i++){
        if (!in[i]) dfs(i);
    }
    reverse(topo.begin(), topo.end());
     
    for (int i = 0; i < (Q + 63) / 64; i++){
        memset(accessable, 0, sizeof(accessable));
        for (int j = i * 64; j < min(Q, (i + 1) * 64); j++){
            accessable[c[j]] |= (1ll << (j % 64));
        }
        for (int j = 0; j < topo.size(); j++){
            for (int k = 0; k < G[topo[j]].size(); k++){
                accessable[G[topo[j]][k]] |= accessable[topo[j]];
            }
        }
        for (int j = i * 64; j < min(Q, (i + 1) * 64); j++){
            if ((accessable[d[j]] >> (j % 64)) & 1) puts("Yes");
            else puts("No");
        }
    }
     
    return (0);
}