Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-02-18

SRM462 1000

| 20:55 | はてなブックマーク -  SRM462 1000 - cafelier@SRM

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;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100218
 | 

presented by cafelier/k.inaba under CC0