백준 17270 연예인은 힘들어 (c++)

조건이 너무 불합리하다

 

 

2번에서 합이 최소인 노드들을 구하고 3번에서 조건을 체크해서 맞는 노드가 없었으면

당연히 차선 노드들에서 3번 조건찾기를 진행해야 하는것 아닌가?

이 문제는 일단 합이 최단인 노드를 뽑아두고 그것들이 전부 3번 조건을 만족하지 못하면 얄짤없이 -1을 출력해야 하는 문제였던 것이다

 

말도안돼..

 

int v, m;
int js, ss;
vector <vector< pair<int, int >> > arr;
vector<int> jihun;
vector<int> sungha;

지헌 성훈 각각의 시점에서 다익스트라를 돌려줄 것이므로 체크 배열을 두개 만들어준다

 

void dijkstra(vector<int>& checker, int start)
{
	checker[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>>pq;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		int dist = -pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (checker[now] < dist)continue;
		for (int i = 0; i < arr[now].size(); i++)
		{
			int cost = arr[now][i].second + dist;
			int next = arr[now][i].first;

			if (checker[next] > cost)
			{
				checker[next] = cost;
				pq.push({ -cost,next });
			}
		}
	}
}

극히 평범한 다익스트라

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	
	cin >> v >> m;
	arr.resize(v+1);
	jihun.resize(v+1, INT_MAX);
	sungha.resize(v+1, INT_MAX);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
		arr[b].push_back({ a,c });
	}
	cin >> js >> ss;

	dijkstra(jihun, js);
	dijkstra(sungha, ss);

각각 출발점에서 다익스트라를 돌려준다

 

priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> pq;
for (int i = 1; i <= v; i++)
{
	if (i == js || i == ss)continue;
	int cost = jihun[i] + sungha[i];
	if (!pq.empty())
	{
		if (cost == -pq.top().first)
		{
			pq.push({ -(jihun[i] + sungha[i]),{-jihun[i],-i} });
		}
		else if (cost < -pq.top().first)
		{
			while (!pq.empty())pq.pop();
			pq.push({ -(jihun[i] + sungha[i]),{-jihun[i],-i} });
		}
	}
	else 
	{
		pq.push({ -(jihun[i] + sungha[i]),{-jihun[i],-i} });
	}
}

조건이 많으므로 우선순위 큐를 또 활용했다

최단시간의 합, 지헌이와 해당 노드사이의 시간, 노드 를 묶어서 - 붙여서 넣어준다

각각의 조건에서 최소가 가장 앞으로 오게된다

 

넣을때 주의한다

최단시간의 합이 더 작은 값이 생기면 이제까지 넣었던 값을 전부 비워줘야 한다

일단 조건2번이 절대적이기 때문이다

	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int node = -pq.top().second.second;
		pq.pop();

		if (jihun[node] <= sungha[node])
		{
			cout << node << '\n';
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

pq에 있는 값들은 일단 최단시간의 합이고

그중에서 지헌이가 성하보다 늦지 않게 도착하는 조건을 검사해준다

 

 

수능지문에서 이런식으로 나오면 소송 걸릴듯;;