백준 1595번, 북쪽나라의 도로 풀이

문제

백준 1595번

풀이

임의의 정점 $ v_{0} $에서 가장 먼 정점 $ v_{1} $을 DFS 또는 BFS로 찾아줍니다.

다시 정점 $ v_{1} $에서 가장 먼 정점 $ v_{2} $를 찾아줍니다.

 

도시 $ v_{1} $과 $ v_{2} $의 거리가 정답이 됩니다.

 

자료형에 유의해줘야하는데, int를 사용하면 12%에서, long long을 사용하면 100%에서 틀렸습니다.

unsigned long long 박으니 풀렸습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef vector<int> vi;
typedef vector<ll> vl;

ull vis[10001];
vector<pull> graph[10001];

void dfs(ull a, ull c) {
	for (const auto &nxt : graph[a]) {
		if (vis[nxt.first]) continue;
		vis[nxt.first] = c + nxt.second;
		dfs(nxt.first, c + nxt.second);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	vector<pair<ull, pull>> vec;

	string str;
	ull v = 0;
	while (getline(cin, str)) {
		if (str.empty() || str == "0") break;

		stringstream ss(str);
		ll a, b, c; ss >> a >> b >> c;
		v = a;
		graph[a].emplace_back(b, c);
		graph[b].emplace_back(a, c);
	}


	ull mx = 0;
	for (ull i = 1; i <= 10000; i++) vis[i] = 0;
	vis[v] = 0;
	dfs(v, 0);
	for (ull i = 1; i <= 10000; i++) {
		if (mx < vis[i]) {
			mx = vis[i];
			v = i;
		}
	}

	for (ull i = 1; i <= 10000; i++) vis[i] = 0;
	vis[v] = 0;
	mx = 0;

	dfs(v, 0);
	for (ull i = 1; i <= 10000; i++) mx = max(mx, vis[i]);

	cout << mx;
}