らての精進日記

修行をします

joi春合宿2014 day1-1:Bus

解法

この問題を解く鍵は多分部分点にあって、部分点の意味(この部分点はこの解法ならとれる、みたいな)を考えながらアルゴリズムを練っていくとうまく解ける感じがあった。(個人的な感想)

小課題1

N,M≦2000 Q=1
バス停1に行く時間の候補はかなり無数にあるように思えるが、実はO(M)個しかない(バス停1から出発する任意のバスの出発時間)
それぞれについてダイクストラをしてみるとO(M^2logN)とかになるので解ける。

小課題2

N,M<=2000
クエリがいっぱいくるが、小課題1に一工夫すれば解ける。O(M)個あるバス停1に行く時間の候補それぞれについて、バス停Nに最短でいつ到着できるかを求める。バス停1に早く着けばつくほどバス停Nにも早く着けるので、この値は単調増加になる。そこで二分探索すれば解ける。
O(M^2logN+QlogM)

小課題3

Q=1
小課題2では、O(M)個ある候補すべてについてバス停Nに到着する時刻を計算して、その値を元に二分探索した。今回はそれをやると死ぬのダメ。
クエリが1個しか来ないので、O(M)個ある候補について全部調べる必要はない。二分探索してO(logM)回だけダイクストラするとO(M(logM)^2)となり解ける。

満点解法

O(M)個ある候補を試してみる時に、時刻が遅い方からダイクストラする。ある時刻の候補についてダイクストラしているときはそれ以前にダイクストラしたときに用いたバスはもう用いないように頑張ってする。なぜこのようなことをするかというと、以前のダイクストラで用いたバスをまた試しても、それまでの結果以下の結果しか得られないからである。このようにすると、全体でO(M)個のバスを調べるだけでO(M)個の候補について最短でいつバス停Nに到着するかが分かる。あとは小課題2と同じように二分探索でクエリに答える。これでO(MlogN+QlogM)くらい(ダイクストラ部分の正確な見積もりかたがわからない)になるので解ける。

コード

#include<bits/stdc++.h>
using namespace std;

struct edge{
    int to,cost,come;
    edge(int a,int b,int c):to(a),cost(b),come(c){}
    bool operator<(const edge &e)const{
        return come<e.come;
    }
};

struct data{
    int pos,cost;
    data(int a,int b):pos(a),cost(b){}
    bool operator<(const data &d)const{
        return cost>d.cost;
    }
};

const int INF=1001001001;

int N,M,Q;
vector<edge>G[100000];
int dist[100000];
int prev[100000];
int memo[300000];
int query[100000];
void input(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b,x,y;
        scanf("%d%d%d%d",&a,&b,&x,&y);
        a--;b--;
        G[a].push_back(edge(b,y-x,x));
    }
    scanf("%d",&Q);
    for(int i=0;i<Q;i++)scanf("%d",&query[i]);
}

void dijkstra(int s){
    dist[0]=G[0][s].come;
    priority_queue<data>Q;
    Q.push(data(0,dist[0]));

    while(Q.size()){
        data d=Q.top();Q.pop();
        if(dist[d.pos]<d.cost)continue;

        for(int &i=prev[d.pos];i<G[d.pos].size();i++){
            edge &e=G[d.pos][i];
            if(dist[d.pos]>e.come)break;
            if(dist[e.to]<=e.cost+e.come)continue;
            dist[e.to]=e.cost+e.come;
            Q.push(data(e.to,dist[e.to]));
        }
    }
    memo[s]=dist[N-1];
}

void solve(){
    for(int i=0;i<N;i++){
        sort(G[i].begin(),G[i].end());
        reverse(G[i].begin(),G[i].end());
    }


    fill_n(dist,N,INF);
    for(int i=0;i<G[0].size();i++)dijkstra(i);

    for(int i=0;i<Q;i++){
        int ub=G[0].size(),lb=-1;
        while(ub-lb>1){
            int mid=(ub+lb)/2;
            if(memo[mid]<=query[i])ub=mid;
            else lb=mid;
        }
        if(ub==G[0].size())puts("-1");
        else printf("%d\n",G[0][ub].come);
    }

}

int main(){
    input();
    solve();
    return 0;
}