취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13271번 문제인 스파이이다.
문제는 아래 링크를 확인하자.

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

문제의 3번 쿼리는 1번 쿼리와 2번 쿼리가 동시에 주어진 것과 같은 것으로 취급할 수 있다.

또한 1번 쿼리의 식의 양변에 -1을 곱하면 2번 쿼리와 같은 형태로 식을 변형할 수 있다.

따라서 입력된 정보들로 xi - xj <= w 와 같은 형태의 식들로 이루어진 system을 얻을 수 있다.

또한, 남은 문제의 제약조건(각 평점의 범위) 또한 위와 같은 식으로 나타낼 수 있다. 구체적으로, 평가가 0(zero)인 가상의 0번 상품이 있다고 생각하면 xi - x0가 0 이상이고 100 이하라고 쓰는 식으로 각 평점의 범위를 제한할 수 있다.

이러한 system을 Bellman-Ford를 이용하여 풀어서 나오는 평점 xi들에는 (해가 존재한다면) 100점이 적어도 하나 있을 수밖에 없다는 점을 확인하자. 또한, (x0가 아닌) 최소 평점을 갖는 xi를 xk라 한다면, xk는 더 커질 수 없다는 점을 확인하자. x0에서 xk까지의 최단경로가 나타내는 부등식 constraints를 생각해보면 된다.

따라서, 100 - xk를 구하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct edge {
	int x, y; ll d;
	edge(int x, int y, ll d) {
		this->x = x, this->y = y, this->d = d;
	}
};

ll dist[1001];
vector<edge> edges;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	
	for (int i = 1; i <= N; i++) {
		edges.emplace_back(i, 0, 0);
		edges.emplace_back(0, i, 100);
	}
	for (int i = 0; i < K; i++) {
		int q, x, y, d; cin >> q >> x >> y >> d;
		if (q == 1) edges.emplace_back(edge(x, y, -d));
		else if (q == 2) edges.emplace_back(edge(y, x, d));
		else {
			edges.emplace_back(edge(x, y, -d));
			edges.emplace_back(edge(y, x, d));
		}
	}

	for (int i = 1; i <= N; i++) dist[i] = 1000000007;
	for (int i = 0; i < N; i++) {
		for (auto &e : edges) {
			if (dist[e.x] < 1000000007) dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
		}
	}

	bool chk = 1;
	for (auto& e : edges) {
		if (dist[e.x] < 1000000007) {
			if (dist[e.y] > dist[e.x] + e.d) chk = 0;
		}
	}

	if (chk) {
		ll mn = 100;
		for (int i = 1; i <= N; i++) mn = min(mn, dist[i]);
		cout << 100 - mn;
	}
	else cout << -1;
}