UVa 10308 Roads in the North

題意：
　　計算該graph最遠的距離。
想法：
　　DFS function 定義為"回傳該點能走的最遠深度"，例如DFS(p點)，則在DFS裡面我們對p點能前往的那些點做DFS，記下該路徑(route)的長度，並一直刷新route_max的大小，最後回傳route_max。
　　在刷新route_max"之前"，我們先把(route+route_max)與ans比較，刷新ans，(route+route_max)表示p點往兩個不同方向的路徑的和，不斷刷新ans，就能產生最遠的距離。

	#include <cstdio>
	#include <vector>
	using namespace std;
	struct point_type{
	int nxt;
	int len;
	};
	vector<point_type> toPoint[10005];
	int ans;
	int DFS(int point, int prev_point) // DFS回傳該點能走的最深路徑的距離
	{
	int route_max = 0;
	for (auto &p : toPoint[point]) {
	if (p.nxt == prev_point) continue;
	int route = DFS(p.nxt, point) + p.len;
	if (route + route_max > ans) // 現在走的路徑+已經儲存的最大路徑如果大於ans就更新ans
	ans = route + route_max;
	if (route > route_max)
	route_max = route;
	}
	return route_max;
	}
	void input(char line[])
	{
	int p1, p2, L;
	sscanf(line, "%d%d%d", &p1, &p2, &L);
	toPoint[p1].push_back({p2,L});
	toPoint[p2].push_back({p1,L});
	}
	int main()
	{
	freopen("input.txt","rt",stdin);
	char line[100];
	while (gets(line)) {
	if (line[0] == '\0') {
	puts("0");
	continue;
	}
	for (auto &v : toPoint) v.clear();
	input(line);
	while (gets(line)) {
	if (line[0] == '\0') break;
	input(line);
	}
	ans = 0;
	DFS(1,-1);
	printf("%d\n", ans);
	}
	return 0;
	}

view raw [UVa] 10308 Roads in the North.cpp hosted with ❤ by GitHub