cafelier@SRM

SRM462 1000

あとで | 20:55 |

wataさんの解法を参考にして書いてみたもの。

typedef int             vert;
typedef int             cost;
typedef pair<cost,vert> edge;
typedef vector<edge>    edges;
typedef vector<edges>   graph;

static const cost INF   = 0x12345678; // large enough but INF+INF<2^31
static const vert START = 0;
static const vert GOAL  = 1;

class WarTransportation { public:
   int messenger(int n, vector <string> highways) 
   {
      return solve( parse(n, highways) );
   }

   graph parse(int n, vector <string> highways)
   {
      graph G(n);

      string hi = accumulate(highways.begin(), highways.end(), string());
      for(int i=0; i<hi.size(); )
      {
         int k = hi.find(',', i);
         if( k == string::npos ) k = hi.size();

         int a, b, c;
         stringstream(hi.substr(i,k-i)) >> a >> b >> c;
         G[a-1].push_back( edge(c,b-1) );

         i = k+1;
      }

      return G;
   }

   int solve( const graph& G )
   {
      // Suppose you reached the city "v", and found there the most critical load is broken.
      // How long will it take a detour to the GOAL?  It's ukai[v]!

      vector<cost> ukai;
      for(int v=0; v<G.size(); ++v)
         ukai.push_back( ukaiDist(G,v) );

      // Compute the least T such that:
      //   we get to the GOAL, making the worst case time <= T?

      cost L=0, R=99999999;
      if( !reachable(G, ukai, R) ) return -1;
      if(  reachable(G, ukai, L) ) return 0;

      // We can when T=R, and cannot T=L. 
      // That is, T in (L, R]. Now let's binary-search!

      while( R-L>1 )
         (reachable(G, ukai, (L+R)/2) ? R : L) = (L+R)/2;
      return R;
   }

   cost ukaiDist( const graph& G, vert v )
   {
      if( v == GOAL )        return 0;
      if( G[v].size() == 0 ) return INF;

      cost worst = 0;
      for(int f=0; f<G[v].size(); ++f) // f : broken road
      {
         priority_queue< edge, vector<edge>, greater<edge> > Q;
         set<vert> V;
         V.insert(v);
         for(int i=0; i<G[v].size(); ++i) // push all loads from v, except f
            if( i != f )
               Q.push( G[v][i] );
         worst = max( worst, dijkstra(G,Q,V) ); // start dijkstraing
      }
      return worst;
   }


   bool reachable( const graph& G, const vector<cost>& ukai, cost ukaiLimit )
   {
      priority_queue< edge, vector<edge>, greater<edge> > Q;
      set<vert> V;
      Q.push( edge(0,START) );
      return dijkstra(G, Q, V, ukai, ukaiLimit) != INF;
   }

   cost dijkstra( const graph& G,
      priority_queue< edge, vector<edge>, greater<edge> >& Q, set<vert>& V,
      const vector<cost>& ukai=vector<cost>(), cost ukaiLimit=-1
   ) {
      while( !Q.empty() )
      {
         // pop
         cost c = Q.top().first;
         vert v = Q.top().second;
         Q.pop();

         // check
         if( V.count(v) || (ukaiLimit>=0 && c+ukai[v]>ukaiLimit) )
            continue;
         if( v == GOAL )
             return c;
         V.insert(v);

         // next
         for(int i=0; i<G[v].size(); ++i)
            if( !V.count(G[v][i].second) )
               Q.push( edge(c+G[v][i].first, G[v][i].second) );
      }
      return INF;
   }
};