解法
よくわからない。最初に乗る辺(バス停 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);
}
}
