1916번: 최소비용 구하기

문제 풀이

 

 최소 비용일때마다 fee 배열에 저장된 최소비용을 갱신해줍니다. fee[finish]에 start node에서 finish node로 가는 최소 비용이 저장됩니다.

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, m, finish;
int fee[1001];
vector <pair<int,int>> graph[1001];
 
int go(int start) {
 
    queue<int> q;
    q.push(start);
    fee[start] = 0;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        for (int i = 0; i < graph[x].size(); i++) {
            int nx, cost;
            nx = graph[x][i].first;
            cost = graph[x][i].second;
            if (fee[nx] == -1 || fee[x] + cost < fee[nx]) {
                fee[nx] = fee[x] + cost;
                if (nx != finish) {
                    q.push(nx);
                }
            }
        }
    }
    return fee[finish];
}
 
int main() {
 
    memset(fee, -1, sizeof(fee));
    cin >> n >> m;
 
    while (m--) {
        int b, e, c; cin >> b >> e >> c;
        graph[b].push_back(make_pair(e, c));
    }
 
    int start; cin >> start >> finish;
 
    cout << go(start) << '\n';
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

1916번: 최소비용 구하기