Submission #140586

#	Time	Username	Problem	Language	Result	Execution time	Memory
140586		khrbuddy03	두 로봇 (KOI18_robot)	C++14	100 / 100	395 ms	25592 KiB

robot

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e5 + 9;
vector<pair<int, int>> tree[inf];
map<pair<int, int>, int> m;
int dist[inf];
int par[inf];
bool vis[inf];

void dfss(int here, int len) {
	dist[here] = len;
	for (auto i : tree[here]) {
		int there = i.first;
		int nlen = len + i.second;
		if (dist[there] == -1) dfss(there, nlen);
	}
}

void dfsm(int here) {
	vis[here] = true;
	for (auto i : tree[here]) {
		if (vis[i.first]) continue;
		dfsm(i.first);
		par[i.first] = here;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, x, y; cin >> n >> x >> y;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c; cin >> a >> b >> c;
		tree[a].emplace_back(b, c);
		tree[b].emplace_back(a, c);
		m[make_pair(a, b)] = c;
		m[make_pair(b, a)] = c;
	}
	fill(&dist[1], &dist[n + 1], -1);
	dfss(x, 0);
	dfsm(x);
	int here = y;
	int mpath = 0;
	while (here != x) {
		mpath = max(mpath, m[make_pair(here, par[here])]);
		here = par[here];
	}
	cout << dist[y] - mpath << '\n';
	
}

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41