SRM 479 500pt: TheAirTripDivOne

TopCoder

問題概要

都市がN(<400)あり、各都市間には片方向への飛行機が定期的に飛んでいる。都市0から都市N-1までの移動時間がT(<10^8)以下になるようなスケジュールで、空港での滞在時間の最小値を最大化する問題。

考えたこと

  • (今でもかなり好きな問題の一つ。当時は通せなかったけどこのとき初めてDijkstraを書いた)
  • 最小値の最大化なのだから定石は二分探索。
  • 滞在時間の最小値を固定したらあとは移動時間T以下にできるかはDijkstraで判定できる。
  • 解空間とかに気をつけて実装する。通らない。
  • Dijkstra書き間違えてた。if(d <= dist[cur])continue;とか一発で終わってしまうだろ…。
  • 修正。無事通った。

practiceで通ったコード

計算量O(log T * E * log E)。

#include <vector>
#include <string>
#include <numeric>
#include <queue>
#include <algorithm>
#include <sstream>
using namespace std;

typedef long long int64;

struct flight{
	int from, to;
	int64 first, time, term;
};

struct state{
	int64 dist;
	int cur;
};

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

const int MAX_N = 477;
const int64 INF = 1LL<<60;

vector<flight> graph[MAX_N];
int64 dist[MAX_N];

struct TheAirTripDivOne {

	int find(int n, vector <string> flights, int time) {
		//グラフ構成
		string line = accumulate(flights.begin(), flights.end(), string());
		for(int i=0; i<(int)line.length(); i++)if(line[i] == ','){
			line[i] = ' ';
		}
		stringstream ss(line);
		int a,b,c,d,e;
		while(ss>>a>>b>>c>>d>>e){
			a--; b--;
			graph[a].push_back((flight){a,b,c,d,e});
		}

		if(!check(1, n, time)){
			return -1;
		}

		int low = 1, high = time + 1;
		while(high - low > 1){
			int mid = (high + low) / 2;
			if(check(mid, n, time)){
				low = mid;
			}
			else{
				high = mid;
			}
		}

		return low;
	}

	bool check(int x, int n, int64 time){
		priority_queue<state> que;
		fill(dist, dist+n, INF);
		dist[0] = 0;
		que.push((state){0, 0});

		while(!que.empty()){
			state tp = que.top(); que.pop();
			int64 d = tp.dist;
			int cur = tp.cur;

			if(cur == n-1){
				return true;
			}
			if(d > dist[cur]){
				continue;
			}

			int64 now = d + (cur==0?0:x);
			for(int i=0; i<(int)graph[cur].size(); i++){
				flight& fly = graph[cur][i];
				int64 next = INF;
				if(now <= fly.first){
					next = fly.first + fly.time;
				}
				else{
					int64 loss = 0;
					if( (now - fly.first)%fly.term != 0){
						loss = fly.term - (now - fly.first)%fly.term;
					}
					next = fly.time + now + loss;
				}

				if(next <= time && dist[fly.to] > next){
					dist[fly.to] = next;
					que.push((state){next, fly.to});
				}
			}
		}

		return false;
	}
};