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

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

1504번: 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

주어진 2개의 정점을 반드시 통과하는 최단경로를 구하는 문제로, 그러한 경로가 없을 때는 -1을 출력하면 된다.

초반에 조금 헤매서 알고리즘 단톡방에 약간의 힌트를 구했던 문제로 추후에 복습이 필요한 문제같다.

1부터 N까지 정점이 존재하고, 주어진 두개의 정점(v1, v2)을 반드시 지나는 최단경로는

1-> v1 -> v2 -> N 

or

1-> v2-> v1-> N

이 될 수 있고, 이 두개의 경로 비용 중 더 작은 값이 최단경로가 되는 것이다.

각각의 시작노드로부터 떨어진 노드거리를 모두 구하는 것이 핵심이 되는 문제이다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include<iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 98765432

using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b){
		if (a.first == b.first) {
			return a.second > b.second;
		}
		else {
			return a.first > b.first;
		}
	}
};

int N, E;

typedef struct graphNode {
	int dest;
	int cost;
	struct graphNode* next;
}GraphNode;

typedef struct graph {
	int count;
	GraphNode* adj;
}Graph;

void Graph_Init(Graph* gph, int count) {
	gph->count = count;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (count + 1));
	for (int i = 1; i <= count; i++) {
		gph->adj[i].next = NULL;
	}
}

int AddDirectedLinked(Graph* gph, int src, int dst, int cost) {
	GraphNode* temp = (GraphNode*)malloc(sizeof(GraphNode));
	temp->dest = dst;
	temp->cost = cost;
	temp->next = gph->adj[src].next;
	gph->adj[src].next = temp;
	return 1;
}

int AddUnDirectedLinked(Graph* gph, int src, int dst, int cost) {
	return AddDirectedLinked(gph, src, dst, cost) && AddDirectedLinked(gph, dst, src, cost);
}

vector<int> Dijkstra(Graph* gph, int start, int end) {
	vector<int> distance(end, INF);
	distance[start] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int prev = pq.top().first;
		int r_start = pq.top().second;
		pq.pop();

		if (distance[r_start] < prev) continue;

		GraphNode* head = gph->adj[r_start].next;
		while (head) {
			if (head->cost + prev < distance[head->dest]) {
				distance[head->dest] = head->cost + prev;
				pq.push({ distance[head->dest], head->dest });
			}
			head = head->next;
		}
	}
	return distance;
}

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

	Graph graph;
	cin >> N >> E;
	Graph_Init(&graph, N); 
	N++;

	for (int i = 0; i < E; i++) {
		int start, end, len;
		cin >> start >> end >> len;
		AddUnDirectedLinked(&graph, start, end, len);
	}

	int s1, s2;
	cin >> s1 >> s2;
	vector<int> result = Dijkstra(&graph, 1, N);
	vector<int> tmp1 = Dijkstra(&graph, s1, N);
	vector<int> tmp2 = Dijkstra(&graph, s2, N);

	int answer = min({ result[s1] + tmp1[s2] + tmp2[N - 1], result[s2] + tmp2[s1] + tmp1[N - 1] });
	if (answer >= INF || answer < 0)
		cout << -1 << '\n';
	else
		cout << answer << '\n';

	return 0;
}