POJ-1724: ROADS

PKU

keyword

A*　RMQ　BIT　C++

問題概要

ノード数V(<100)の有向グラフがある。各辺には距離(L<100)とコスト(C<100)の2つの属性がある(E<10^4)。コストの総和がK(<10^4)以下になるような経路のうち、最小の距離を求める問題。

解法

ノード番号とコストを組にしてDijkstraすればよさげ。今回は、コストを気にしなかった場合の最小値が楽に計算できるのでA*で組んだ。また、ノード番号とコストの組を全部考えると計算量が怪しいので枝刈りっぽいことをする。

あるノードに関して、黒い点が既に確定してる点。黒で塗りつぶされた部分にある状態(赤い点)は明らかに最適解の一部となりえないのでそいつらはqueueに突っ込まない。逆に青や緑の点はqueueに突っ込む。新しい状態をqueueに突っ込むかどうかは、[0..cost]における最小値より距離が小さいかどうかで判断する。となるとこれはRMQである。
普通RMQはsegment treeとか平方分割で実装するけど、今回は区間が[0..cost]で、左端が固定されているのでBITっぽくできる(追記:本当は上手くいかない。a_iをより大きな値で更新した場合の処理が不完全。この問題に限っていえばそんな状況は起きないから大丈夫だけど)。この辺はアリ本参照のこと。
ちなみにコストを気にしなかった場合の目的地までの最小値はWarshall-Floydでやっているけど、計算量減らしたかったら辺の向きを逆にして目的地からDijkstraすればいい。実装量は増えるけど。
計算量は…どの位なんだろう？

感想

A*にしても計算量が劇的に変わることはないし、最短距離の見積りがおかしいとむしろ遅くなることもある。なので基本はDijkstraで、A*は最後の手段としておくのが良さそう。

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = 1<<28;
const int MAX_N = 102;

struct edge{
    int to, dist, cost;
    edge(int _t, int _d, int _c):to(_t), dist(_d), cost(_c){}
};

struct state{
    int cur, dist, cost;
    state(int _c, int _d, int _co):cur(_c), dist(_d), cost(_co){}
};

bool operator<(const state& a, const state& b){
    return a.dist > b.dist;
}

int graph[MAX_N][MAX_N];
vector<edge> G[MAX_N];
int bit[MAX_N][10009];
int N, K;

void buildRMQ(){
    for(int i=0; i<N; i++)for(int j=0; j<10009; j++)
        bit[i][j] = INF;
}

//[1..cost]
int query(int v, int cost){
    int ret = INF;
    while(cost>0){
        ret = min(ret, bit[v][cost]);
        cost -= cost & -cost;
    }
    return ret;
}

void change(int v, int cost, int dist){
    while(cost<10009){
        bit[v][cost] = min(bit[v][cost], dist);
        cost += cost & -cost;
    }
}

int solve(){

    for(int k=0; k<N; k++)for(int i=0; i<N; i++)for(int j=0; j<N; j++)
        graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
    for(int i=0; i<N; i++) graph[i][i] = 0;
    if(graph[0][N-1] == INF) return -1;

    buildRMQ();

    priority_queue<state> Q;
    Q.push(state(0,graph[0][N-1],0));
    while(!Q.empty()){
        int cur = Q.top().cur, dist = Q.top().dist-graph[cur][N-1],
            cost = Q.top().cost; Q.pop();
        if(cur==N-1) return dist;
        if(query(cur,cost+1)<dist) continue;
        for(int i=0; i<G[cur].size(); i++){
            int ncur = G[cur][i].to, ndist = dist + G[cur][i].dist,
                ncost = cost + G[cur][i].cost;
            if(graph[ncur][N-1] < INF && ncost <= K
                    && query(ncur,ncost+1)>ndist){
                change(cur,cost+1,dist);
                Q.push(state(ncur,ndist+graph[ncur][N-1],ncost));
            }
        }
    }

    return -1;
}

int main(){
    int R;
    scanf("%d%d%d",&K,&N,&R);
    for(int i=0; i<N; i++)for(int j=0; j<N; j++) graph[i][j] = INF;
    for(int i=0; i<R; i++){
        int x, y, d, c;
        scanf("%d%d%d%d",&x,&y,&d,&c);
        x--;y--;
        G[x].push_back(edge(y,d,c));
        graph[x][y] = min(graph[x][y], d);
    }
    printf("%d\n",solve());
    return 0;
}