반응형

www.acmicpc.net/problem/1916

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

[ 백준 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]);
}

 

반응형
Posted by 명문코딩컴퓨터
,