SRM 492 :: DIV2

日記書くの久しぶりだなぁ…。

1000pt

問題概要
traveling salesmanさんが、N個(0...N-1)の街を周ってビジネスしたいんだってよ！
街と街の間の道路は一本しかなく、双方向に移動できるってさー。
驚くことにtraveling salesmanさんはあの伝説のジョンタイター本人で、タイムマシンを1つ持っている。
一度訪れた街なら何度でもタイムマシンで移動できる、羨ましい！
そして本題だが、N個全ての街を周るときの最小移動距離を天才プログラマーの貴方に求めてほしい。
あ、traveling salesmanさんの初期位置は0番目の街だよ！
それと、タイムマシンによる移動距離は含めないとする。
街の最大数が1000個だよー。街と街を繋ぐ距離のコストは最大で10000000だよー。

だいたいこんな感じ、ぜんぜん違うけど。

解法：
やるだけ、という名の最小全域木問題

#include <略>

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()

int road[1000][1000];

class TimeTravellingSalesman{
public:
   long long determineCost(int N, vector <string> roads){
      string in,tmp;
      rep(i,roads.size())in += roads[i];
      rep(i,N)rep(j,N)road[i][j]=-1;
      
      stringstream ss(in);
      while(ss>>tmp){
         int a,b,c;
         sscanf(tmp.c_str(),"%d,%d,%d",&a,&b,&c);
         road[a][b] = road[b][a] = c;
      }
      
      vector<int> vnode;
      int vcheck[1000];
      memset(vcheck,0,sizeof(vcheck));
      vnode.pb(0);
      vcheck[0]=1;
      
      long long ret = 0;
      for(;;){
         int next_id=-1, t_cost=999999999;
         rep(i,vnode.size()){
            rep(j,N)if( road[vnode[i]][j]!=-1 && !vcheck[j] && t_cost>road[vnode[i]][j] ){
               t_cost = road[vnode[i]][j];
               next_id = j;
            }
         }
         if( next_id==-1 ) break;
         vnode.pb( next_id );
         vcheck[next_id] = 1;
         ret += (long long)t_cost;
      }
      
      if( vnode.size()!=N ) return -1;
      return ret;
   }
};