[백준] 24042 - 횡단보도

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

24042번: 횡단보도

 

골드 1까지 되는 문제인지는 잘 모르겠다.

이 문제는 다익스트라로 해결할 수 있는데, 가중치가 동적으로 변경된다.

즉, 주기에 맞지 않게 정점을 방문하면 다음 주기(+m)에 다음 정점을 방문할 수 있다는 뜻이다.

 

1. 그래서 현재 주기에 갈 수 있는지 없는지를 판단한 후에 -> ((i.second - cost) % m + m) % m
2. 이동하는 시간을 더하면 된다 -> + 1

1. 에서 식을 저렇게 짠 이유는, 언어마다 나머지 연산을 다른 방식으로 해결하기 때문이다.

그래서 많은 WA를 받았고 결국 저렇게 계산하였다. 즉, (i.second - cost) % m < 0 이어도 올바르게 결과가 도출된다.

 

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

vector<vector<pair<int, long long>>> v;
vector<long long> dis;
int main()
{
	int n, m;
	cin >> n >> m;
	v.resize(n + 1);
	dis.resize(n + 1, LLONG_MAX);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back({b, i});
		v[b].push_back({a, i});
	}

	priority_queue<pair<long long, int>> pq;
	pq.push({0, 1});
	dis[1] = 0;

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

		for (auto &i : v[node])
		{
			int nxNode = i.first;
			long long nxCost = cost + ((i.second - cost) % m + m) % m + 1;

			if (dis[nxNode] > nxCost)
			{
				dis[nxNode] = nxCost;
				pq.push({-nxCost, nxNode});
			}
		}
	}

	cout << dis[n];
}