[BOJ-1753]최단경로

다익스트라 알고리즘을 사용하는 문제.

시작 정점부터 각 정점에 이르는 최소비용은 얼마인지 구하는 문제이다. 

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
#include<memory.h>
#define mp(a,b) make_pair(a,b)
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VP;
 
const int INF = 0x7FFFFFFF;
const int VMAX = 20001;
 
int main(){
    int numOfV, numOfE;
    scanf("%d%d", &numOfV, &numOfE);
 
    VP E[VMAX];
    // Vertex ; cost, vis, path
    VVI V = VVI(numOfV+1, VI(3, 0));
    for(int i = 1 ; i <= numOfV ; i++){
        V[i][0] = INF;
        V[i][2] = -1;
    }
    
    int start;
    scanf("%d", &start);
    V[start][0] = 0; // start Vertex Cost is 0
 
    for(int i = 0 ; i < numOfE ; i++){
        int u,v,w;
        scanf("%d%d%d", &u, &v, &w);
        E[u].push_back(mp(v,w));
    }
 
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    Q.push(mp(0,start));
 
    while(!Q.empty()){
        PII p = Q.top(); Q.pop();
        int here = p.second;
        if(V[here][1] != 0) continue;
        V[here][1] = 1;
 
        for(auto iter = E[here].begin() ; iter != E[here].end() ; iter++){
            PII p = *iter;
            int there = p.first;
            int cost = p.second;
 
            if(V[there][0] > V[here][0] + cost){
                V[there][0] = V[here][0] + cost;
                V[there][2] = here;
                Q.push(mp(V[there][0], there));
            }
        }
    }
 
    for(int i = 1 ; i <= numOfV ; i++){
        if(V[i][0] == INF) printf("INF");
        else printf("%d",V[i][0]);
        puts("");
    }
 
    //for(int i = 1 ; i <= numOfV ; i++){
    //    for(int parent = i ; parent != -1 ; parent = V[parent][2]){
    //        printf("%d ",parent);
    //    }
    //    puts("");
    //} // path 
 
    return 0;
}
 

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
 
typedef long long LLD;
typedef vector<LLD> VLL;
typedef pair<LLD, LLD> PLL;
typedef vector<PLL> VPLL;
typedef pair<LLD, PLL> PLPLL;
typedef vector<bool> VB;
const LLD INF = 9999999999;
VPLL edge[22222];
VLL vertex;
int main(){
    int n,m; scanf("%d%d", &n, &m);
    int s; scanf("%d", &s);
    vertex = VLL(n+1, INF);
    vertex[s] = 0;
    for(int i = 0 ; i < m ; i++){
        LLD u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        edge[u].pb(mp(w,v));
    }
    
    priority_queue<PLL, VPLL, greater<PLL> > Q;
    Q.push(mp(0,s));
 
    while(!Q.empty()){
        PLL h = Q.top(); Q.pop();
        LLD here = h.second;
        LLD cost = h.first;
        
        if(vertex[here] < cost) continue;
 
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            PLL p = *iter;
            LLD there = p.second;
            LLD t_cost = cost + p.first;
            if(vertex[there] > t_cost){
                vertex[there] = t_cost;
                Q.push(mp(t_cost, there));
            }
        }
    }
 
    for(int i = 1 ; i <= n ; i++){
        if(vertex[i] != INF) printf("%lld\n", vertex[i]);
        else puts("INF");
    }
    return 0;
}