SRM479 div1 medium

二部探索＋ダイクストラ。

#include <algorithm>
#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <utility>

using namespace std;
typedef long long LL;

int n;
LL limit;
LL INF=((LL)1<<LL(50));
LL visited[500];
vector<int> F[500];
vector<int> T[500];
vector<int> P[500];
vector<int> D[500];

class TheAirTripDivOne 
{
	public:

		bool check(LL wait)
		{
			for(int i=0;i<n;i++)
				visited[i]=INF;
			priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > que;
			que.push(make_pair(0,0));

			bool succes=false;
			while(!que.empty())
			{
				LL now=que.top().first;
				int pos=que.top().second;
				que.pop();

				if(visited[pos]<now || limit<now)
					continue;
				else if(pos==n-1)
				{
					succes=true;
					break;
				}
				else
				{
					visited[pos]=now;
					if(pos!=0)
						now+=wait;
					else
						;

					for(int i=0;i<F[pos].size();i++)
						if(F[pos][i]!=INF)
						{
							LL ne=F[pos][i]+((now<F[pos][i])?0:
								(now-F[pos][i]+P[pos][i]-1)/P[pos][i]*P[pos][i])+T[pos][i];
							que.push(make_pair(ne,D[pos][i]));
						}
				}
			}
			return succes;
		}

		int find(int _n, vector <string> flights, int time) 
		{
			limit=time;
			n=_n;

			for(int i=0;i<500;i++)
				F[i].clear(),T[i].clear(),P[i].clear(),D[i].clear();

			string input;
			for(int i=0;i<flights.size();i++)
			{
				for(int j=0;j<flights[i].size();j++)
					if(flights[i][j]==',')
						flights[i][j]=' ';
				input+=flights[i];
			}
			stringstream ss(input);
			int a,b,f,t,p;
			while(ss >> a >> b >> f >> t >> p)
			{
				a--,b--;
				F[a].push_back(f);
				T[a].push_back(t);
				P[a].push_back(p);
				D[a].push_back(b);
			}

			int ceil=time,bottom=1;
			while(5<ceil-bottom)
			{
				int wait=(ceil+bottom)/2;

				if(check(wait))
					bottom=wait;
				else
					ceil=wait;
			}
			for(int i=ceil;bottom<=i;i--)
				if(check(i))
					return i;

			return -1;
		}
};