백준 #11779 최소비용 구하기 2

백준 #11779 최소비용 구하기 2

어느 정점에서 다른 정점까지 가는 최소비용과 도달하는 데 방문한 정점의 수와 정점을 출력하는 문제.

다익스트라 알고리즘을 사용하여 풀 수 있다. 경로가 수정될 때마다 직전에 방문한 정점을 prevVisited 배열에 저장한 후, 역순으로 출력한다.

#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#define INF 1e8

using namespace std;

int n, m, start, dest;
vector<pair<int, int>> graph[1001];
int dist[1001];
vector<int> prevVisited(1001);
stack<int> path;

void makePath(int num) {
    if(num != 0) {
        path.push(num);
        makePath(prevVisited[num]);
    }
}

void printPath() {
    while(!path.empty()) {
        cout << path.top() << ' ';
        path.pop();
    }
}

void dijkstra() {
    fill(dist, dist + 1001, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push({-dist[start], start});
    while(!q.empty()) {
        int here = q.top().second;
        q.pop();
        for(int i = 0; i < graph[here].size(); i++) {
            int next = graph[here][i].first;
            int nextCost = graph[here][i].second;
            if(dist[next] > dist[here] + nextCost) {
                dist[next] = dist[here] + nextCost;
                q.push({-dist[next], next});
                prevVisited[next] = here;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    cin >> m;
    for(int i = 0; i < m; i++) {
        int from, to, val;
        cin >> from >> to >> val;
        graph[from].push_back({to, val});
    }
    cin >> start >> dest;
    dijkstra();
    cout << dist[dest] << '\n';
    makePath(dest);
    cout << path.size() << '\n';
    printPath();
    return 0;
}

---

2021.07.13 재채점

이게 무슨일이람 재채점 했더니 시간 초과라니

데이터를 추가해 재채점했더니 시간 초과가 됐다는 알림이 떴다. 그래서 시간을 더 줄일 수 있는 방법을 생각해보았는데, 다음과 같다.

출발 도시, 도착 도시, 그리고 비용을 입력받을 때

1. 이미 입력받은 노선보다 비용이 크다면 그래프에 추가를 하지 않는 것
2. 이미 입력받은 노선보다 비용이 작다면 그것으로 수정하는 것

이렇게 하면 특정 도시 A에서 B까지 가는 버스 노선은 그래프에 한 개밖에 저장이 되지 않는다.
최종 수정 코드는 아래와 같다.

#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#define INF 1e8

using namespace std;

int n, m, start, dest;
vector<pair<int, int>> graph[1001];
int dist[1001];
vector<int> prevVisited(1001);
stack<int> path;

void makePath(int num) {
    if(num != 0) {
        path.push(num);
        makePath(prevVisited[num]);
    }
}

void printPath() {
    while(!path.empty()) {
        cout << path.top() << ' ';
        path.pop();
    }
}

void dijkstra() {
    fill(dist, dist + 1001, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push({-dist[start], start});
    while(!q.empty()) {
        int here = q.top().second;
        q.pop();
        for(int i = 0; i < graph[here].size(); i++) {
            int next = graph[here][i].first;
            int nextCost = graph[here][i].second;
            if(dist[next] > dist[here] + nextCost) {
                dist[next] = dist[here] + nextCost;
                q.push({-dist[next], next});
                prevVisited[next] = here;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    cin >> m;
    for(int i = 0; i < m; i++) {
        int from, to, val;
        cin >> from >> to >> val;
///////////////////////////////////////////////////////////////////////////
//추가한 코드
        bool plzAdd = true;
        for(int i = 0; i < graph[from].size(); i++) {
            if(graph[from][i].first == to) {
                plzAdd = false;
                if(graph[from][i].second > val) { //입력받은 비용이 더 작을 시 수정
                    graph[from][i].second = val;
                }
                break;
            }
        }
        if(plzAdd) {
            graph[from].push_back({to, val});
        }
    }
//////////////////////////////////////////////////////////////////////////////
    cin >> start >> dest;
    dijkstra();
    cout << dist[dest] << '\n';
    makePath(dest);
    cout << path.size() << '\n';
    printPath();
    return 0;
}