백준 1916번 - 최소비용 구하기 소스 코드 - 우선순위 큐

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

[ 백준 1916번 최소비용 구하기 - 우선순위 큐 + 다익스트라 ]

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int d[1001];
bool check[1001];
vector<pair<int, int>> in[1001];

int main() 
{
    int n, m, a, b;
    int x, y, z;
    int i;
    
    //입력 
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) 
	{
        scanf("%d %d %d", &x, &y, &z);
        in[x].push_back(make_pair(y, z));
    }    
    scanf("%d %d", &x, &y);
    
	//우선순위 큐 선언    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
	//초기화    
    for (int i = 1; i <= n; i++) {
        d[i] = 0x7fffffff;
    }
    d[x] = 0;
    q.push(make_pair(0, x));
    
    while (!q.empty()) 
	{
        a = q.top().second;  //도시 
        q.pop();
        
        if (check[a] == false) 
		{
            check[a] = true;
            for (i = 0; i< in[a].size(); i++)
			{
                b = in[a][i].first;  //비용  
                if (d[b] > d[a] + in[a][i].second) 
				{
                    d[b] = d[a] + in[a][i].second;
                    q.push(make_pair(d[b], b));
                }
            }
        }
    }
    printf("%d\n", d[y]);
}