[백준 C++] 15808 주말 여행 계획

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

난이도

P5

유형

다익스트라

풀이

사실 이게 왜 P5인지 모르겠는데 p랑 q중 적은 쪽 모두에서 다익스트라를 돌려주면 된다. p+q는 n보다 작으므로 최댓값은 n/2이다. 시간복잡도는 O(VElogV)이긴 한데 /2가 무시할만한 그건 아니다. 충분히 돌아갈것 같았다. p에서 돌렸으면 q노드들 확인, q에서 돌렸으면 p노드들 확인해주면 된다.

정답이 음수가 될 수 있다. (이게 왜..)

#include <iostream>
#include <queue>
#include <algorithm>

#define MAX 1001
#define INF 1000000001

using namespace std;

vector<pair<int, int>> graph[MAX];
vector<pair<int, int>> pp;
vector<pair<int, int>> qq;


int dijk(int N,vector<pair<int, int>> start, vector<pair<int, int>> end)
{
	int elen = end.size();
	int mx,ans = -INF;
	for (auto s : start)
	{
		int now, cost, vi[MAX];
		for (int i = 1; i <= N; i++) vi[i] = INF;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		pq.push(make_pair(0, s.first));
		vi[s.first] = 0;


		while (!pq.empty())
		{
			cost = pq.top().first;
			now = pq.top().second;
			pq.pop();
			if (vi[now] < cost) continue;
			for (auto nextp : graph[now])
			{
				if (vi[nextp.first] > cost + nextp.second)
				{
					vi[nextp.first] = cost+nextp.second;
					pq.push(make_pair(vi[nextp.first], nextp.first));
				}
			}
		}
		mx = -INF;
		for (auto endp : end)
		{
			mx = max(endp.second + s.second - vi[endp.first], mx);
		}
		ans = max(ans, mx);
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int n, c,p,q;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> c;
			if (c != 0)
			{
				graph[i].push_back(make_pair(j, c));
			}
		}
	}
	int loc, exp;
	cin >> p >> q;
	for (int i = 0; i < p; i++)
	{
		cin >> loc >> exp;
		pp.push_back(make_pair(loc, exp));
	}
	for (int i = 0; i < q; i++)
	{
		cin >> loc >> exp;
		qq.push_back(make_pair(loc, exp));
	}
	if (pp.size() < qq.size())
	{
		cout << dijk(n, pp, qq);
	}
	else
	{
		cout << dijk(n, qq, pp);
	}

}