백준 1504: 특정한 최단 경로

boj1504

주어진 두 정점을 반드시 지나는 최단 경로를 구하는 문제. 주어진 두 정점을 각각 v1, v2라 하면 1->v1->v2->N와 1->v2->v1->N 중 작은 값을 출력하면 된다. 그리고 각 노드까지는 다익스트라를 적용하면 된다.

만약 경로가 없을 때에는 -1을 출력해야 하는데, 1차 시도에서는 이 부분을 고려하지 않아 틀렸다. 1에서 N까지 이동할 때 다익스트라를 세 번 돌리기 때문에 경로가 존재하지 않는 경우에는 INF+INF+INF를 리턴에 오버플로가 발생할 수 있기 때문. 그래서 올바른 범위인지 체크하는 범위를 만들어 최종 계산값이 0 미만이거나 INF 이상인 경우는 -1을 출력할 수 있도록 했다.

#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 801
#define INF 987654321
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[FROM] = < <to, cost> <to, cost> , ...>

bool noRoute(int n) {
	if (n < 0 || n >= INF) return true;
	else return false;
}

void update(int from, int old, vector<int> * dist, priority_queue< pair<int, int> > * pq) {
	int edge = graph[from].size();
	int i;

	for (i = 0; i < edge; i++) {
		int to = graph[from][i].first;
		int cost = graph[from][i].second;
		int newDist = old + cost;

		if (newDist < (*dist)[to]) {
			(*dist)[to] = newDist;
			pq->push(make_pair(-newDist, to));
		}
	}
}

vector<int> dijkstra(int src, int dst) {
	vector<int> dist(MAX, INF);
	priority_queue< pair<int, int> > pq; // (-cost, from)
	dist[src] = 0;
	pq.push({ 0, src });

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

		if (dist[from] < cost) continue;
		else update(from, cost, &dist, &pq);
	}
	return dist;
}

int calc(int src, int v1, int v2, int dst) {
	return dijkstra(src, v1)[v1] + dijkstra(v1, v2)[v2] + dijkstra(v2, dst)[dst];
}

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

	int N, E, v1, v2, from, to, c, i;
	cin >> N >> E;

	for (i = 0; i < E; i++) {
		cin >> from >> to >> c;
		graph[from].push_back(make_pair(to, c));
		graph[to].push_back(make_pair(from, c));
	}
	cin >> v1 >> v2;

	int a = calc(1, v1, v2, N); // 1->v1->v2->N
	int b = calc(1, v2, v1, N); // 1->v2->v1->N
    
	if (noRoute(a) && noRoute(b)) cout << -1 << endl;
	else cout << ((a < b) ? a : b) << endl;
	return 0;
}

Share on: