題目
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
There are N cities and N-1 roads in Magic-Island. You can go from one city to any other. One road only connects two cities. One day, The king of magic-island want to visit the island from the capital. No road is visited twice. Do you know the longest distance the king can go.
Input
There are several test cases in the input
A test case starts with two numbers N and K. (1<=N<=10000, 1<=K<=N). The cities is denoted from 1 to N. K is the capital.
The next N-1 lines each contain three numbers X, Y, D, meaning that there is a road between city-X and city-Y and the distance of the road is D. D is a positive integer which is not bigger than 1000.
Input will be ended by the end of file.
Output
One number per line for each test case, the longest distance the king can go.
Sample Input
3 1
1 2 10
1 3 20
Sample Output
20
題目大意
N個城市蛮寂、(N-1)條路的島，K為首都蝴乔。從K出發(fā)齐蔽，每條路只走一遍倍啥，問走過的最大距離锣光。
思路
用變量maxDistance存所求最大距離炉爆。DFS搜索每個路徑，當(dāng)當(dāng)前路徑大于maxDistance時岂津，當(dāng)即更新。
代碼
// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087).
// sicily 1024: http://soj.sysu.edu.cn/1024
#include <cstdio>
#include <vector>
#define MAX_SIZE 10000
using namespace std;
struct Road {
int id_; // road id.
int end_; // the other end of the road
int length_; // the length of the road
Road(int id, int end, int length) {
id_ = id;
end_ = end;
length_ = length;
}
};
int maxDistance;
vector<Road> Roads[MAX_SIZE + 1]; // Roads[0] is useless
bool visited[MAX_SIZE + 1]; // visited[0] is also useless
// DFS searching the roads. for the implementation is recursive, the closed list
// have to be global.
// @Param start: a city that begin the visit.
// @Param pathLength: gets a certain path's length. if the path is longer than
// the max distance we knows, update the maxDistance.
void DFS(int start, int pathLength = 0) {
// for each road connected to start
for (int i = 0; i < Roads[start].size(); i++) {
// if the road is not visited
if (!visited[Roads[start][i].id_]) {
// visits it
visited[Roads[start][i].id_] = true;
// adds the road length to the path length
pathLength += Roads[start][i].length_;
// update the max distance
if (pathLength > maxDistance) maxDistance = pathLength;
// continue the path from the other end of the road
DFS(Roads[start][i].end_, pathLength);
// [IMPORTANT] back tracking
pathLength -= Roads[start][i].length_;
visited[Roads[start][i].id_] = false;
}
}
}
int main() {
// the cities' number N and the capital's number K
int N, K;
while (scanf("%d %d", &N, &K) != EOF) {
// initialization.
maxDistance = 0;
for (int i = 0; i <= MAX_SIZE; i++) {
Roads[i].clear();
visited[i] = false;
}
// gets the total N-1 roads.
int start, end, length;
for (int i = 1; i < N; i++) {
scanf("%d %d %d", &start, &end, &length);
// bidirenctional roads
Roads[start].push_back(Road(i, end, length));
Roads[end].push_back(Road(i, start, length));
}
// DFS the roads from the capital.
DFS(K);
// output the max distance visited.
printf("%d\n", maxDistance);
}
return 0;
}
