[백준] 11779 최소 비용 구하기2 dijkstra

문제 :

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

분석 :

이번 문제는 전 문제 1916번

2021.03.10 - [Algorithm🐰/백준] - [백준] 1916 최소비용 구하기 dijkstra

에 거쳐간 노드를 출력할 수 있도록 추가하는 작업이 필요하다. 

따라서 while 문 안 for 문에 t 배열을 하나 추가해 그 전 노드를 인덱스 값으로 현재 노드의 값을 넣어주고

그 전 pop해온 노드(now)를 값으로 받도록 하였다.

출력할 때에는 end인덱스부터 route 벡터에 담긴다. 그래서 역순으로 벡터를 출력해도록 하였다, 

 

 

c++ 코드 :

//
//  11779_min_cost2.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/10.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define INF 1e9

vector<pair<int, int>>vertex[1001];
int d[100001]; // 최단 거리 테이블
int t[100001];

void min_bus(int start, int end){
    priority_queue<pair<int, int>>pq;
    pq.push(make_pair(0, start));
    d[start] = 0;
    while(!pq.empty()){
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < vertex[now].size(); i++){
            
            int cost = dist + vertex[now][i].second;
            if(cost < d[vertex[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[vertex[now][i].first] = cost;
                t[vertex[now][i].first] = now; // 전 노드가 부모 노드 가지고 있도록
                
                pq.push(make_pair(-cost,vertex[now][i].first));
            }
        }
    }
    
}

int main(){
    int city;
    cin >> city;
    int bus;
    cin >> bus;
    for(int i = 0 ; i < bus; i++){
        int in, to, cost;
        cin >> in >> to >> cost;
        vertex[in].push_back({to, cost});
    }
    
    int start, end;
    cin >> start >> end;
    fill(d, d+100001, INF);
    
    min_bus(start, end);
    cout << d[end] << '\n';
    
    vector<int>route;
    
    int temp_end = end;
    
    while (temp_end)
    {
        route.push_back(temp_end);
        temp_end = t[temp_end];
    }
    cout << route.size() << endl;
    for (int i = ((int)route.size()) - 1; i >= 0; i--) cout << route[i] << " ";
    cout << endl;

    return 0;
}