백준 17396(백도어)

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

17396번: 백도어

 

N개의 분기점이 있다. 이 분기점만 지날 수 있으며, 만약에 와드가 있으면 지나가지 못한다. 

 

0 -> N-1까지가는 최단 거리를 구하여라.

 

최단거리 문제는 다익스트라

 

따라서 다익스트라로 구현한다. 여기서 N값이 10만이므로 인접행렬로는 구현이 불가능하다는 것을 알 수 있다 따라서 인접리스트를 이용한 다익스트라로 구현한다.

 

와드에 대한 처리는 단순하게 와드가 있다면 그 곳은 가지 못하므로 아예 받지 않았다. 

 

다 익스트라의 개념을 다시 설명하면, 

 

0에서 나머지 지점으로 가는 거리 배열을 dist[]라고 하자.

이 배열은 처음에 인접한 경우만 집어넣어서 만약에 경로가 없으면 문제에서 요구하는 최대 거리보다 큰 값인 INF값으로 넣어준다. 

 

이 배열을 priority_queue에 넣고, 최소거리를 가진 지점을 토대로 조사한다. 

 

조사를 한다는 것은 거리를 계산하는 일이다. 

A->B를 가는 거리와 A->C->B로 가는 거리를 비교해서 만약에 후자가 더 작으면 A->B까지 가는 최소거리(dist[B]) 를 최신화해주고, 이 값과 index를 다시 priority_queue에 집어넣는다. pq가 empty가 될때까지 반복한다. 

 

이때 조사한 지점은 visited[] =true로 만들어줘서 후에 다시 조사하지 않도록 해준다. (먼저 조사하는 것이 최소다)

 

 

이 과정들을 지나고 나면 각 지점까지의 최소거리 배열 dist[]가 완성된다. 

 

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
#define MAX 100000

int N, M, a,b,c;
long long INF = 9223372036854775807;
long long dist[MAX];
vector<pair<long long, long long> > vec[MAX];
priority_queue<pair<long long, long long> > pq;
pair<long long , long long> p;
bool cango[MAX] = { false };
bool visited[MAX] = { false };

void solve() {
	for (int i = 0; i < vec[0].size(); i++) {
		pq.push(make_pair(-vec[0][i].first, vec[0][i].second));
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (!visited[p.second]) {
			visited[p.second] = true;
			for (int i = 0; i < vec[p.second].size(); i++) {
				if (dist[vec[p.second][i].second] > dist[p.second] + vec[p.second][i].first) {
					dist[vec[p.second][i].second] = dist[p.second] + vec[p.second][i].first;
					pq.push(make_pair(-dist[vec[p.second][i].second], vec[p.second][i].second));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 0) cango[i] = true;
	}
	cango[N - 1] = true;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		if (!cango[a] || !cango[b]) continue;
		vec[a].push_back(make_pair(c, b));
		vec[b].push_back(make_pair(c, a));
		if (a == 0) dist[b] = c;
		if (b == 0) dist[a] = c;
	}
	for (int i = 1; i < N; i++) {
		if (dist[i] == 0) dist[i] = INF;
	}
	solve();
	if (dist[N - 1] == INF)cout << "-1\n";
	else
		cout << dist[N - 1] << "\n";

}

 

여기서 주의해야 할 점은 최대 값을 구하는 일이다. 

최대거리는 길의 수 * 가능한 최대의 값

300,000 * 100,000

이므로 3*10^10 

30,000,000,000 300억이므로 이 값을 초과한 값이 INF값이 된다. 따라서 int 범위인 21억을 초과하므로 더 큰 자료형을 써주자. 

 

그리고 또 만약에 INF의 자료형만 바꿔주면 INF가 들어갈 수 있는 그리고 비교될 수 있는 경우에서 원치않은 결과가 나타날 수 있으므로 그냥 모조리 바꿔주자.