[BOJ/Gold 4] 백준 32770 집 가고 싶다(C++)

문제 링크

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

 

문제

세종이는 오늘따라 집이 너무 가고 싶어서 외출을 하기로 했다. 학교와 집을 왕복할 때는 버스를 이용하는데, 귀교 시간에 맞춰 돌아오기 위해서는 학교에서 집으로 갔다가, 학교로 다시 돌아오는 데 걸리는 시간을 알아야 한다.

세종에는 E개의 버스 노선이 있다. 각 노선의 버스는 정해진 출발 정류장에서 도착 정류장으로만 이동하며, 반대 방향으로는 이동하지 않는다. 단, 세종이는 정말 운이 좋아서 정류장에 도착하면 언제나 바로 원하는 버스에 탈 수 있다. (와! 정말 부럽다)

최대한 오래 집에 있고 싶어 하는 세종이를 위해 학교에서 집으로 다시 집에서 학교로 돌아오는데 걸리는 최소 시간을 구해주자.

 

입력

첫째 줄에 버스 노선의 수 E가 주어진다. (3 ≤ E ≤ 210,000)

그다음 E개의 줄에 걸쳐 각 노선의 출발 정류장의 이름 u, 도착 정류장의 이름 v, 이동 시간을 나타내는 정수 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 10^9)

 u, v는 영문 대소문자 및 숫자로 이루어진 20자 이내의 문자열이며, 서로 다른 두 정류장이 이름이 같은 경우는 없다.

정류장의 이름 중에는 반드시 sasa와 home이 포함된다. sasa는 학교, home은 집을 의미한다.

 

출력

첫째 줄에 학교에서 집으로 갔다가 다시 집에서 학교로 돌아오는 데 걸리는 최소 시간을 출력한다.

만약 그런 경로가 없다면 대신 첫째 줄에 -1을 출력한다.

 

예제 입력 1

7
sasa busstop 2
busstop home 3
home store 5
store sasa 2
sasa library 1
library store 3
store home 2

예제 출력 1

12

예제 입력 2

3
sasa home 2
home store 3
library sasa 2

예제 출력 2

-1

 

알고리즘 분류

• 자료 구조
• 최단 거리 알고리즘

 

풀이

가지치기는 꼭 해줘야 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define MAX 420001
#define INF 1e15
#define LL long long
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int E, W, N, S, H;
string U, V;
unordered_map<string, int> UM;
vector<pair<int, LL> > Edges[MAX];
LL Dist[MAX][2];
LL Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < 2; j++) {
            Dist[i][j] = INF;
        }
    }
    Answer = INF;
}

void input() {
    cin >> E;
    for (int i = 0; i < E; i++) {
        cin >> U >> V >> W;
        if (UM.find(U) == UM.end()) {
            UM.insert(make_pair(U, ++N));
            if (U == "sasa") {
                S = N;
            }
            if (U == "home") {
                H = N;
            }
        }
        if (UM.find(V) == UM.end()) {
            UM.insert(make_pair(V, ++N));
            if (V == "sasa") {
                S = N;
            }
            if (V == "home") {
                H = N;
            }
        }
        Edges[UM[U]].push_back(make_pair(UM[V], W));
    }
}

void dijkstra() {
    priority_queue<pair<LL, pair<int, int> > > PQ;
    Dist[S][0] = 0;
    Dist[H][1] = 0;
    PQ.push(make_pair(0, make_pair(S, 0)));
    PQ.push(make_pair(0, make_pair(H, 1)));
    
    while (!PQ.empty()) {
        LL NowD = -PQ.top().first;
        int NowX = PQ.top().second.first;
        int NowMode = PQ.top().second.second;
        PQ.pop();
        
        if (Dist[NowX][NowMode] < NowD) {
            continue;
        }
        
        for (int i = 0; i < (int)Edges[NowX].size(); i++) {
            int NextX = Edges[NowX][i].first;
            LL NextD = Edges[NowX][i].second;
            if (Dist[NextX][NowMode] > Dist[NowX][NowMode] + NextD) {
                Dist[NextX][NowMode] = Dist[NowX][NowMode] + NextD;
                PQ.push(make_pair(-Dist[NextX][NowMode],make_pair(NextX, NowMode)));
            }
        }
    };
}

void settings() {
    dijkstra();
    if ((Dist[H][0] != INF) && (Dist[S][1] != INF)) {
        Answer = Dist[H][0] + Dist[S][1];
    }
}

void printAnswer() {
    if (Answer == INF) {
        cout << "-1\n";
    }
    else {
        cout << Answer << "\n";
    }
}

int main() {
    FASTIO
    init();
    input();
    settings();
    printAnswer();
    
    return 0;
}