[BOJ 15808 // C++] 주말 여행 계획

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

 

이번에 볼 문제는 백준 15808번 문제인 주말 여행 계획이다.
문제는 아래 링크를 확인하자.

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

15808번: 주말 여행 계획

(출발지점 가중치) - (두 노드 사이 거리) + (도착지점 가중치)를 최대화하는 문제이다.

 

-(출발지점 가중치) + (두 노드 사이 거리)를 최소화한 값을 multi source일 때의 최단거리 알고리즘을 이용하여 값을 구한 다음, 각 도착지점에서 위 값을 이용하여 최댓값 후보들을 구하는 것으로 문제를 해결하자.

 

처음에는 계산실수로 floyd-warshall 알고리즘으로도 통과될 거라고 예상하고 풀이를 시도했으나 시간초과를 받았다.

 

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, P, Q;
vector<pair<int, int>> G[1001];

int dist[1001];
bool visited[1001];
priority_queue<pair<int, int>> pq;

void dijkstra() {
	while (!pq.empty()) {
		auto& p = pq.top();
		int cur = p.second, d = -p.first;
		pq.pop();
		if (d > dist[cur]) continue;

		for (auto& pp : G[cur]) {
			int node = pp.first, w = pp.second;
			if (visited[node] == 0) {
				dist[node] = d + w;
				visited[node] = 1;
				pq.push(make_pair(-(d + w), node));
			}
			else if (dist[node] > d + w) {
				dist[node] = d + w;
				pq.push(make_pair(-(d + w), node));
			}
		}
	}
}

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

	cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int x; cin >> x;
			if (x) G[r].emplace_back(make_pair(c, x));
		}
	}

	cin >> P >> Q;
	while (P--) {
		int x, w; cin >> x >> w;
		visited[x] = 1;
		dist[x] = -w;
		pq.push(make_pair(w, x));
	}

	dijkstra();

	int ans = -1000000007;
	while (Q--) {
		int x, w; cin >> x >> w;
		ans = max(ans, -dist[x] + w);
	}

	cout << ans;
}