백준 3830 / C++

https://www.acmicpc.net/problem/3830

3830번: 교수님은 기다리지 않는다

 

[ 풀이 ] 

오프라인 쿼리로 계산해주면 쉽다.  unkown은 미리 처리해주는것에 유의하자. 

거리를 그래프에 담은 후 dfs로 순회하면서 연결된 것끼리 거리를 전처리해주고 차이를 구하면 된다.

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 100010;
ll n, m, a, b, w;
ll par[MAX], dist[MAX], vis[MAX], no[MAX];
vector<pair<ll, ll>>g[MAX];
struct query { ll a, b; }; // ! query
query qr[MAX];

struct Union_find {
	int find(int u) {
		return par[u] == -1 ? u : par[u] = find(par[u]);
	}
	void uni(int u, int v) {
		u = find(u), v = find(v);
		if (u != v) par[v] = u;
	}
}uf;

// DFS
void dfs(int x, ll d) {
	vis[x] = 1;
	dist[x] = d;
	for (auto [nx, w] : g[x]) {
		if (vis[nx])continue;
		dfs(nx, d + w);
	}
}

// 초기화
void init() {
	for (int i = 1; i < MAX; i++) {
		g[i].clear();
		vis[i] = 0;
		dist[i] = 0;
		par[i] = -1;
		no[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	while (1) {
		cin >> n >> m;
		if (!n && !m) break;
		init();
		int idx = 1;
		while (m--) {
			char op; cin >> op;
			if (op == '!') {
				cin >> a >> b >> w;
				uf.uni(a, b);
				g[a].push_back({ b, w });
				g[b].push_back({ a, -w }); 
			}
			else {
				cin >> a >> b;
				qr[idx] = { a, b };
				if (uf.find(a) != uf.find(b)) no[idx] = 1; // 미리 처리 
				idx++;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) dfs(i, 0);
		}
		for (int i = 1; i < idx; i++) {
			auto [p, q] = qr[i];
			if (no[i]) {
				cout << "UNKNOWN\n";
			}
			else {
				cout << dist[q] - dist[p] << '\n';
			}
		}
	}
}