순간을 성실히, 화려함보단 꾸준함을

[ boj : 2982 ]국왕의 방문 본문

알고리즘,SQL/백준,BOJ

[ boj : 2982 ]국왕의 방문

폭발토끼 2021. 1. 27. 18:24

www.acmicpc.net/problem/2982

 

2982번: 국왕의 방문

지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안

www.acmicpc.net

문제 : 국왕이 방문하는데 이때 교차로 사이의 도로는 국왕이 먼저 건너면 건널 수 없습니다.

이때 상그니가 목적지까지 최소시간으로 갈 수 있는 시간을 구하시오

 

해설 : 아우 전 문제를 잘못 읽어서 엄청 고생했었습니다. 교차로에는 공유 가능하나 교차로 사이의 도로가 겹치면 안되는 것 입니다. 이때도, 상그니가 먼저 교차로에는 들어갈 수 있습니다. 

무조건 국왕이 먼저 도로를 건너면 건너지 못합니다.

 

다익스트라 알고리즘을 사용해서 구하면 되는데 국왕이 지나가는 도로를 처리를 해주어야겠죠.

먼저 국왕이 지나는 도로를 언제부터 언제까지 건널 수 없는지 범위로 전처리로 해주고 나서 다익스트라를 돌려 하나씩 구분지어 가며 답을 도출해 나아가면 됩니다.

 

만약 국왕이 지나고 있어 지나갈 수 없는 상태라면 국왕이 도로를 다 지나갈때동안 기다리고 나서 건너면 되죠.

 

#include<bits/stdc++.h>

using namespace std;

struct a {
	int s, e;
}A[1001][1001];

struct info {
	int to, weight;
	bool operator<(const info& cur) const {
		return weight > cur.weight;
	}
};

int n, m;
int a, b, k, g;
int arr[1000],dist[1001];
int cp[1001][1001];
vector<info> v[1001];

const int INF = (int)1e9;
int dijk();

int main()
{
	int x, y, z;
	cin >> n >> m >> a >> b >> k >> g;
	for (int i = 0; i < g; i++)cin >> arr[i];
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		v[x].push_back({ y,z });
		v[y].push_back({ x,z });
		cp[x][y] = cp[y][x] = z;
	}
	int prefix = 0;
	for (int i = 1; i < g; i++) {
		int p = arr[i - 1];
		int q = arr[i];

		A[p][q].s =A[q][p].s= prefix;
		prefix += cp[p][q];
		A[p][q].e = A[q][p].e = prefix;
	}
	cout<<dijk()-k;
	return 0;
}
int dijk()
{
	for (int i = 1; i <= n; i++)dist[i] = INF;

	priority_queue<info> pq;
	dist[a] = k;
	pq.push({ a,k });

	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (dist[cur.to] < cur.weight)continue;

		for (int i = 0; i < v[cur.to].size(); i++) {
			int next = v[cur.to][i].to;
			int next_weight = v[cur.to][i].weight;
			
			if (dist[next] > dist[cur.to] + next_weight) {
				if (A[cur.to][next].s <= dist[cur.to] && dist[cur.to] < A[cur.to][next].e) {
					dist[next] = A[cur.to][next].e + next_weight;
				}
				else
					dist[next] = dist[cur.to] + next_weight;
				pq.push({ next,dist[next] });				
			} 
		}
	}
	return dist[b];
}

추가로 저가 항상 찝찝했던 부분이 정점간의 간선을 표현할때 필요가 없는 부분을 어쩔 수 없이 감안하고 배열을 써야된다는게 싫었는데(메모리때문에) 이를 해결해 줄 수 있는 기가막힌 방법을 봤네요....

앞으로 이렇게 이용하시면 될 것 같습니다.

 

*djm03718님의 코드입니다.(감사합니다)

#include <bits/stdc++.h>
using namespace std;

struct A {
	int i, w;
	bool operator<(const A &o) const {
		return w > o.w;
	}
};

map<int, int> adj[1005], mp[1005];
int seq[1005];
int d[1005];
const int inf = (int)1e9;

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

	int n, m, a, b, k, g, i;
	cin >> n >> m >> a >> b >> k >> g;

	for (i = 0; i < g; i++)
		cin >> seq[i];
	for (i = 0; i < m; i++)
	{
		int u, v, l;
		cin >> u >> v >> l;
		adj[u][v] = adj[v][u] = l;
	}

	int cur = 0, t = 0;
	for (i = 0; i < g; i++)
	{
		int x = seq[i];
		if (i != 0)
		{
			mp[cur][x] = mp[x][cur] = t;
			t += adj[cur][x];
		}
		cur = x;
	}
	for (i = 1; i <= n; i++)
		d[i] = inf;
	d[a] = k;

	priority_queue<A> pq;
	pq.push({ a, k });
	while (pq.size())
	{
		A cur = pq.top();
		pq.pop();
		if (d[cur.i] != cur.w)
			continue;
		for (auto x : adj[cur.i])
		{
			int w = cur.w;
			auto it = mp[cur.i].find(x.first);
			if (it != mp[cur.i].end() && it->second <= cur.w)
				w = max(w, it->second + x.second);
			w += x.second;
			if (w < d[x.first])
			{
				d[x.first] = w;
				pq.push({ x.first, d[x.first] });
			}
		}
	}
	cout << d[b] - k;
}

'알고리즘,SQL > 백준,BOJ' 카테고리의 다른 글

[ boj : 1976] 여행 가자  (0) 2021.01.28
[ boj : 14395 ] 4연산  (0) 2021.01.28
[ boj : 1503 ] 세 수 고르기  (0) 2021.01.27
[ boj : 17208] 카우버거 알바생  (0) 2021.01.25
[ boj : 14225 ]부분수열의 합  (0) 2021.01.23