夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

SRM144 Div.2 1000

散々考えあぐねて…

ギブアップ。


1100点のコードを。


和訳は重要な部分だけコッチにしました。

まぁつまりfromJunctionから対応するtoJunctionへ行けて、その移動にかかる時間をductLengthとしてるわけです。
それで一番早くすべてのJunctionを回ったときの時間というわけですが…

まず思いついたのが単純な深さ優先探索

ただ、これは実装できずに終了。

で考えに考えて、すべての距離を二倍して、一つだけ往復しなくてもいいところがあるからみたいに考えたんですが…
難しいパターンを考えると例外がありそうでやめ。

最後に幅優先と深さ優先のあわさった謎のグラフが自分の頭の中で出来てたりしましたが…


結局二つめの考え方でよかったんですね。

class PowerOutage {
	public:
	int max;
	
	void dfs(int index, int sum, vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength) {
		bool chk=0;
		
		int n=fromJunction.size();
		int i;
		
		for (i=0; i<n; i++) {
			if (fromJunction[i]==index) {
				chk=1;
				dfs(toJunction[i], sum+ductLength[i], fromJunction, toJunction, ductLength);
			}
		}
		if (chk==0) {
			if (max<sum) {
				max=sum;
			}
		}
	}
	
	int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
		int res;
		int sum;
		
		int n=fromJunction.size();
		int i;
		
		max=0;
		sum=0;
		
		dfs(0, sum, fromJunction, toJunction, ductLength);
		
		res=0;
		for (i=0; i<n; i++) res+=ductLength[i];
		res *= 2;
		res -= max;
		
		return res;
	}
};

深さ優先でjunction0から一番離れている場所を求めればいいんですね。
でもコレだと例えば下のような時に

  1 -2
 /  /
0 -3 -4
 \
  5-6

最初の0-1-2しか調べてくれない様な気がするんですが・・・なんで大丈夫なんでしょう?

追記:あ、breakしてないからそんな事ありませんでしたね(笑)