[백준 1753]최단 경로

홍시홍 2020. 1. 9. 22:42

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

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두

www.acmicpc.net

요구사항

1. 각 정점까지의 최소거리

풀이

1. 다익스트라 기본 문제

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

struct go {
    int x;
    int y;
};
int dist[300001];
int n,m;
int startnode;
vector<go> v[20001];
int main(){
    cin>>n>>m;
    cin>>startnode;
    for(int i=0 ; i < m ; i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    priority_queue<pair<int,int>> q;
    q.push({0,startnode});
    for(int i=1; i<=n ; i++){
        dist[i]=987654321;
    }
    dist[startnode]=0;

    while(!q.empty()){
        int cost = -q.top().first;
        int node = q.top().second;
        q.pop();
        for(int i=0 ; i <v[node].size();i++){
            int next=v[node][i].x;
            int c = cost +v[node][i].y;
            if(dist[next]>c){
                dist[next]=c;
                q.push({-c,next});
            }
        }
    }

    for(int i=1; i<=n ; i++)
    {
        if(dist[i]==987654321){
            printf("INF\n");
        }
        else{
            printf("%d\n",dist[i]);
        }
        
    }

}