[BAE/<JOON> 문제풀이] 1504. 특정한 최단 경로

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

1504번: 특정한 최단 경로

핵심::
Dijkstra 기본 문제

풀이::
각각의 경유지를 c1, c2 라고 할때 
s -> c1 -> c2 -> e의 거리와 s -> c2 -> c1 -> e 의 거리 중 더 짧은 것을 출력한다.

의견::

다익스트라 코드 잘못짰다가 틀렸습니다 18연속 매드무비 찍고 겨우 고침

 

코드::

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long;

struct node {
	ll dest;
	ll dist;
};
vector<vector<node>> arr;

const ll MaxVal = -1;

int v, e;

struct cmp {
	bool operator () (node a, node b) {
		return a.dist > b.dist;
	}
};

ll dijkstra(int s, int e) {

	priority_queue<node, vector<node>, cmp> pq;
	vector<ll> cost = vector<ll>(v + 1);

	for (int i = 1; i <= v; i++) {
		cost[i] = MaxVal;
	}

	cost[s] = 0;
	pq.push({ s, 0 });

	while (!pq.empty()) {
		node cur = pq.top(); pq.pop();
		if (cur.dest == e) {
			return cur.dist;
        }
	
        cost[cur.dest] = cur.dist;
		for (auto it : arr[cur.dest]) {
			if (cost[it.dest] != MaxVal) continue;
			pq.push({ it.dest, it.dist + cur.dist });
		}
	}

	return MaxVal;
}

int main()
{
	int i;
	cin >> v;
	cin >> e;
	arr.resize(v + 1);
	for (i = 1; i <= e; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b, c });
		arr[b].push_back({ a, c });
	}

	int c1, c2;

	cin >> c1 >> c2;	

	ll sc1 = dijkstra(1, c1);
	ll c1c2 = dijkstra(c1, c2);
	ll c2v = dijkstra(c2, v);

	ll course1 = sc1 + c1c2 + c2v;
	if (sc1 == -1 || c1c2 == -1 || c2v == -1) {
		course1 = 2100000000;
	}

	ll sc2 = dijkstra(1, c2);	
	ll c1v = dijkstra(c1, v);	

	ll course2 = sc2 + c1c2 + c1v;
	if (sc2 == -1 || c1c2 == -1 || c1v == -1) {
		course2 = 2100000000;
	}

	ll dap = (course1 < course2 ? course1 : course2);

	cout << (dap == 2100000000 ? -1 : dap);

	return 0;
}