SRM479 Div1 Medium(500) TheAirTripDivOne

TheAirTripDivOne

最小の待ち時間をなるべく長くすることでフライトの遅れに対して安全になる、ということだろうか？
二分探索。safetyをある値として、timeまでに街nに辿り着けるかを調べる。

#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <sstream>

using namespace std;

class TheAirTripDivOne
{
public:
    int find( int n, vector <string> flights, int time );
};

int TheAirTripDivOne::find( int n, vector <string> flights, int time )
{
    vector<int> A, B, F, T, P;

    string flight = accumulate( flights.begin(), flights.end(), string() );
    replace( flight.begin(), flight.end(), ',', ' ' );
    stringstream ss( flight );
    int a, b, f, t, p;
    while ( ss >> a >> b >> f >> t >> p )
        A.push_back( a ),  B.push_back( b ),  F.push_back( f ),
        T.push_back( t ),  P.push_back( p );

    int sl = 0;
    int sr = time;

    while ( sr - sl > 1 )
    {
        int s = ( sl + sr ) / 2;

        vector<long long> city( n+1, time+1 );
        city[1] = 1;

        bool up;
        do
        {
            up = false;

            for ( int i=0; i<(int)A.size(); i++ )
            {
                long long t = city[A[i]];
                if ( A[i] != 1 )
                    t += s;
                if ( t <= F[i] )
                    t = F[i];
                else
                    t = ( t - F[i] + P[i] - 1 ) / P[i] * P[i] + F[i];
                t += T[i];

                if ( city[B[i]] > t )
                    city[B[i]] = t,
                    up = true;
            }
        }
        while ( up );

        if ( city[n] < time+1 )
            sl = s;
        else
            sr = s;
    }
    
    return sl > 0 ? sl : -1;
}