メンバー > SGHR > topcoder > PowerOutage


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題


ジャンル

グラフ

解説

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

コード

  1. #include<cmath>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<string>
  5. #include<sstream>
  6. #include<vector>
  7. #include<iostream>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<stack>
  12. #include<list>
  13. #include<algorithm>
  14. using namespace std;
  15.  
  16. #define MAX_V 50
  17.  
  18. class PowerOutage {
  19. public:
  20. vector< vector< pair<int, int> > > connect;
  21.  
  22. int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
  23. connect.resize(MAX_V);
  24. for(int i=0; i<fromJunction.size(); i++){
  25. connect[fromJunction[i]].push_back(make_pair(toJunction[i], ductLength[i]));
  26. }
  27. return dfs(0);
  28. }
  29.  
  30. int nodecost(int i){
  31. int c = 0;
  32. for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
  33. c += it->second + nodecost(it->first);
  34. }
  35. return c;
  36. }
  37.  
  38. int dfs(int i){
  39. int min = 10000000;
  40. for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
  41. int c = 0;
  42. c += it->second + dfs(it->first);
  43. for(vector< pair<int,int> >::iterator jt = connect[i].begin(); jt != connect[i].end(); jt++){
  44. if(it != jt) c += 2*jt->second + 2*nodecost(jt->first);
  45. }
  46. min = min < c ? min : c;
  47. }
  48. if(min == 10000000) min = 0;
  49. return min;
  50. }
  51. };
  52.