문제 링크
https://www.acmicpc.net/problem/17396
문제
유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.
최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.
입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.
입력
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)
두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.
다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다. 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.
출력
첫 번째 줄에 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간을 출력한다. 만약 상대 넥서스까지 갈 수 없으면 -1을 출력한다.
예제 입력 1
5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1
예제 출력 1
12
위 그래프의 최단거리는 0-2-3-4 를 지나는 시간인 5(2+2+1) 이지만, 3번 분기점이 상대의 시야에 있기 때문에 0-2-1-4를 지나는 시간인 12(2+4+6)이 최소 시간이 된다.
예제 입력 2
5 7
0 1 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1
예제 출력 2
-1
알고리즘 분류
- 최단 거리 알고리즘
풀이
정점이 10만개고 간선이 30만개이기 때문에 다익스트라로 최단 거리를 찾을 때 X지점까지 가는 데 걸리는 거리를 기록한 수치가 현재 큐에 들어있는 거리보다 작으면 continue해주지 않으면 시간 제한에 걸린다.
코드
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e12
using namespace std;
int N, M;
vector<pair<int, LL> > Edge[MAX];
bool Ward[MAX];
LL Cost[MAX];
void Input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
Cost[i] = INF;
int A;
cin >> A;
Ward[i] = (A == 1) ? true : false;
}
for (int i = 0; i < M; i++) {
int A, B, C;
cin >> A >> B >> C;
if (Ward[A] || Ward[B]) {
if ((A != N - 1) && (B != N - 1)) {
continue;
}
}
Edge[A].push_back(make_pair(B, C));
Edge[B].push_back(make_pair(A, C));
}
}
void Settings() {
priority_queue<pair<LL, int> > PQ;
PQ.push(make_pair(0, 0));
Cost[0] = 0;
while (!PQ.empty()) {
LL CurCost = -PQ.top().first;
int CurX = PQ.top().second;
PQ.pop();
if (Cost[CurX] < CurCost) {
continue;
}
for (int i = 0; i < Edge[CurX].size(); i++) {
LL nextCost = Edge[CurX][i].second;
int nextX = Edge[CurX][i].first;
if (Cost[nextX] > CurCost + nextCost) {
Cost[nextX] = CurCost + nextCost;
PQ.push(make_pair(-Cost[nextX], nextX));
}
}
};
}
void Find_Answer() {
if (Cost[N - 1] == INF) {
cout << -1 << "\n";
}
else {
cout << Cost[N - 1] << "\n";
}
}
int main() {
FASTIO
Input();
Settings();
Find_Answer();
return 0;
}
'BOJ > Gold' 카테고리의 다른 글
[BOJ/Gold 4] 백준 9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다(C++) (0) | 2022.02.20 |
---|---|
[BOJ/Gold 5] 백준 20168 골목 대장 호석 - 기능성(C++) (0) | 2022.02.19 |
[BOJ/Gold 5] 백준 14284 간선 이어가기 2(C++) (0) | 2022.02.19 |
[BOJ/Gold 5] 백준 14221 편의점(C++) (0) | 2022.02.18 |
[BOJ/Gold 5] 백준 11909 배열 탈출(C++) (0) | 2022.02.18 |