백준 11900 차이 그래프

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

11900번: 차이 그래프

 

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

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

1753번: 최단경로

다익스트라 알고리즘을 사용하는 문제입니다. 다익스트라를 공부하고 오세요.

 

 

 

1. 핵심 아이디어

u → v로 가는 간선이 존재하면 (u+1)%N → (v+1)%N으로 가는 간선도 존재합니다!!

 

위의 사실을 토대로 생각해보면

a → b → c의 과정을 통해서 a → c로 이동하는 경로가 존재한다면

(a+1)%N → (b+1)%N → (c+1)%N를 통해서 (a+1)%N → (c+1)%N로 이동하는 경로 또한

존재한다는 것을 확인할 수 있고 두 경로의 길이는 같을 것 입니다.

 

위의 아이디어를 통해서 이해하기 편한 한 가지 예시를 들자면

(N = 5)

1 → 0로 가는 경로는 0 → 4로 표현될 수 있습니다.

((1 + 4)%N = 0), ((0 + 4)%N = 4) 

 

한 번의 다익스트라만으로 해당 문제를 풀 수 있습니다.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

////////////////////////////////////////////////////////////////////////

const int MAX = 2003;
int Dist[MAX];
int N, Q;
int A[MAX];

//다익스트라
void Dijkstra()
{
	//초기화
	for (int i = 0; i < MAX; i++)
		Dist[i] = INF;

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

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

		pq.pop();

		if (Dist[u] < cost)
			continue;

		for (int v = 0; v <= N - 1; v++)
		{
			if (u == v)
            		{
           				//같은 노드는 넘어간다.
				continue;
			}

			if (u - v >= 1)
			{
            			//u가 v보다 클 경우 처리
				int AV = A[u - v];
				if (AV == 0)
                			{
                				//간선이 없는 경우 넘어간다.
					continue;
                			}
				int nextDis = cost + AV;

				if (Dist[v] > nextDis)
				{
					Dist[v] = nextDis;
					pq.push({ -nextDis, v });
				}
			}
			else
			{
                			//u가 v보다 작을 경우 처리
				int AV = A[u - v + N];
				if (AV == 0)
                			{
                				//간선이 없는 경우 넘어간다.
					continue;
                			}
				int nextDis = cost + AV;

				if (Dist[v] > nextDis)
				{
					Dist[v] = nextDis;
					pq.push({ -nextDis, v });
				}
			}
		}
	}
}

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

	std::cin >> N;
	for (int i = 1; i <= N - 1; i++)
		std::cin >> A[i];

	Dijkstra();

	std::cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		int a, b;
		std::cin >> a >> b;
		
		int ans = -1;

		//nb : a를 0으로 만들었을때의 b의 값
		if (a > b)
       		{
        			int nb = b + (N - a);
			ans = Dist[nb];
        		}
		else
        		{
        			int nb = b - a;
			ans = Dist[nb];
        		}

		//정답을 출력
		std::cout << (ans == INF ? -1 : ans) << endl;
	}
}