JOI春合宿2014 Day1-1 Bus

解法

よくわからない。
最初に乗る辺(バス停 1 から生えてるやつ) を決めて、それぞれの最短到着時刻をダイクストラで求める。
普通にやると遅くなるのは自明なので、あらかじめ辺を遅い順にソートしておくと、嬉しくなる(日本語難しいからソースコード(ry )。前の辺に乗った時よりも到着時刻が早くなっていれば、そのときの到着時刻と出発時刻をデキューに突っ込む。早くなってなければ、そのバスに乗っても意味がなさそうだから無かったことにする。
各クエリに答える時間はにぶたんでいい感じに求まる。
オーダーよくわかんない。

ソース

#include<bits/stdc++.h>  
using namespace std;
const int INF = 1 << 30;
 
struct Edge{
  int to, st, gr;
  bool operator<(const Edge& e)const{
    return st < e.st || (st == e.st && gr < e.gr);
  }
};
typedef vector< vector< Edge > > Graph;
typedef pair< int , int > Pi;
 
Graph info;
vector< int > min_time;
 
int Dijkstra(int idx){
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.push( Pi( info[0][idx].gr, info[0][idx].to));
  min_time[0] = info[0][idx].st;
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.second + 1 == info.size()) return p.first;
    if(p.first > min_time[p.second]) continue;
    for(int i = 0; i < info[p.second].size(); ++i){
      Edge& e = info[p.second][i];
      if(e.st < p.first) break; //バスの出発時刻のほうが早い
      if(min_time[e.to] <= e.gr) continue;
      min_time[e.to] = e.gr;
      que.push( Pi( e.gr, e.to));
    }
  }
  return -1;
}
 
 
int main(){
 
  //A: 出発バス停, B: 到着バス停, X: 出発時刻, Y: 到着時刻
 
  int N, M;
  int A, B, X, Y;
  int Q, L;
 
  scanf("%d %d", &N, &M);
  info.resize(N);
  min_time.resize(N, INF);
 
  for(int i = 0; i < M; ++i){
    scanf("%d %d %d %d", &A, &B, &X, &Y);
    --A, --B;
    info[A].push_back( (Edge){ B, X, Y});
  }
 
  for(int i = 0; i < N; ++i){
    sort(info[i].rbegin(), info[i].rend());
  }
 
  deque< Pi > good;
  
  int prev = INF;
  for(int i = 0; i < info[0].size(); ++i){
    int accept = Dijkstra(i); //Pi(到着時刻, 出発時刻)
    if(accept == -1) continue;
    else if(prev > accept){
      prev = accept;
      good.push_front( make_pair(prev, info[0][i].st));
    }
  }
  good.push_front( make_pair( -1, -1));
 
 
  scanf("%d", &Q);
  while(Q--){
    scanf("%d", &L);
    deque< Pi >::iterator it = lower_bound( good.begin(), good.end(), make_pair( L + 1, -INF));
    --it; //到着時刻直近で出発時刻が小さいもの
    printf("%d\n", it -> second);
  }
}