1916번-최소 비용 구하기

문제

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

1916번: 최소비용 구하기

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int INF = 987654321;
const int MAX = 1001;
vector<pair<int,int>> edge[MAX];
ll dist[MAX];
int n, m;
 
int main(void)
{
    fastio;
    cin >> n >> m;
 
    for(int i = 0; i < m; i++)
    {
        int st, ed, value;
        cin >> st >> ed >>value;
        edge[st].push_back({value, ed});
    }
    
    fill(dist, dist + MAX, INF);
    int start, finish;
    cin >> start >> finish;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0,start});
    dist[start] = 0;
 
    while(!pq.empty())
    {
        int cur = pq.top().second;
        ll cost = pq.top().first;
        pq.pop();
 
        if(dist[cur] < cost)
            continue;
 
        for(auto idx : edge[cur])
        {
            int neighbor = idx.second;
            ll neighborCost = idx.first + cost;
            if(dist[neighbor] > neighborCost)
            {
                dist[neighbor] = neighborCost;
                pq.push({neighborCost, neighbor});
            }
        }
    }
    cout << dist[finish] << "\n";
}