[C++] Dijkstra algorithm / 백준 1504번 - 특정한 최단 경로

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

1504번: 특정한 최단 경로

---

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

const int INF = 1e10;



int n, e;
int visited[1000];
int SL[1000];
int ST1[1000], ST2[1000];

class tpl {
public:
	int a, b, l;
};

vector<tpl> ED[1000];

class pkt {
public:
	int a, b, l;
};

struct comp {
	bool operator()(pkt A, pkt B) {
		if (A.l > B.l)
			return true;
		return false;
	}
};

priority_queue<pkt, vector<pkt>, comp> pq;

void dijk(int s) {
	pkt p, q; int i;
	p.a = 0; p.b = s; p.l = 0;
	pq.push(p);
	for (i = 0; i <= n; i++) {
		SL[i] = INF;
	}

	while (!pq.empty())
	{
		p = pq.top();	pq.pop();
		if (visited[p.b]) continue;

		visited[p.b] = 1; SL[p.b] = p.l;
		for (i = 0; i < ED[p.b].size(); i++) {
			q.l = SL[p.b] + ED[p.b][i].l;
			q.a = p.b;
			q.b = ED[p.b][i].b;
			pq.push(q);
		}
	}
}

int main()
{
	int i, from, to, wei;
	tpl tmp;
	cin >> n >> e;
	for (i = 0; i < e; i++) {
		cin >> from >> to >> wei;
		tmp.a = from; tmp.b = to; tmp.l = wei; ED[from].push_back(tmp);
		tmp.a = to; tmp.b = from; tmp.l = wei; ED[to].push_back(tmp);
	}

	// 1 -> 정점까지 최단거리를 담은 배열 SL을 구하기 위한 첫 번째 다익스트라.
	dijk(1);

	// 1 -> v1 & 1 -> v2 까지 & 1 -> n 까지 의 최소 거리 구함.
	int v1 = 0, v2 = 0;
	long long ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0, result = 0;
	cin >> v1 >> v2;
	ans1 = SL[v1];	ans2 = SL[v2], ans3 = SL[n], ans4 = SL[n];

	// v1에서 n까지 가는 최소 거리 & v2에서 n까지 가는 최소 거리.
	int end1 = 0, end2 = 0;

	// 두 번째 다익스트라를 위한 세팅. v1<->v2 간의 최소 거리를 구하기 위한 두 번째 다익스트라.
	memset(visited, 0, sizeof(visited));
	bool check1 = false;
	dijk(v1);	end1 = SL[n];
	// v1 <-> v2는 반드시 포함되어야 하기 때문에 미리 더해줌.
	int temp = ans1;
	if (SL[v2] == INF) check1 = true;
	
	ans1 = (ans2 + SL[v2] + end1);	ans2 = (temp + SL[v2]);
	ans3 += SL[v2]; ans4 += (SL[v2] + SL[n]);

	// 세 번째 다익스트라. v2 -> n까지의 거리 구하기 위함.
	memset(visited, 0, sizeof(visited));
	dijk(v2);	end2 = SL[n];
	ans2 += end2;	ans3 += end2;

	// 네 번째 다익스트라. n -> v1 or n -> v2를 구하기 위함.
	memset(visited, 0, sizeof(visited));
	dijk(n); 
	//1 -> n -> v1 -> v2
	ans3 += SL[v1];
	// 1 -> n -> v2 -> v1
	ans4 += SL[v2];


	// answer 4가지 경우의 수를 비교해서 최솟값 출력
	result = min({ ans1, ans2, ans3, ans4 });

	if (result == INF || check1) cout << -1;
	else cout << result << '\n';

	return 0;
}

총 4가지 경우를 생각해야하고, 다익스트라는 4번썼다. 너무 지쳐서 코드를 정리할 생각을 못함.

(1) 1 -> v1 -> v2 -> n

(2) 1 -> v2 -> v1 -> n

(3) 1 -> n -> v1 -> v2 -> n

(4) 1 -> n -> v2 -> v1 -> n

 

쉬워보였는데 시간을 너무 많이 썼음. 다익스트라 여러번 사용할 때, memset과 INF를 적절하게 분배해줘야할듯.