メンバー/SGHR/topcoder/PowerOutage - 阪大理学部科学計算・開発サークル -Circle for Science Caluculation and Development-

問題

ジャンル

グラフ

解説

ループのないグラフが与えられ、すべてのノードを回る最小コストの経路を求めよ、という問題。
深さ優先探索で解く。

コード

#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;
 
#define MAX_V 50
 
class PowerOutage {
public:
  vector< vector< pair<int, int> > > connect;
 
  int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
    connect.resize(MAX_V);
    for(int i=0; i<fromJunction.size(); i++){
      connect[fromJunction[i]].push_back(make_pair(toJunction[i], ductLength[i]));
    }
    return dfs(0);
  }
 
  int nodecost(int i){
    int c = 0;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      c += it->second + nodecost(it->first);
    }
    return c;
  }
 
  int dfs(int i){
    int min = 10000000;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      int c = 0;
      c += it->second + dfs(it->first);
      for(vector< pair<int,int> >::iterator jt = connect[i].begin(); jt != connect[i].end(); jt++){
	if(it != jt) c += 2*jt->second + 2*nodecost(jt->first);
      }
      min = min < c ? min : c;
    }
    if(min == 10000000) min = 0;
    return min;
  }
};