[해커랭크] Dijkstra: Shortest Reach 2 (C++)

문제 링크: www.hackerrank.com/challenges/dijkstrashortreach/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=7-day-campaign

Dijkstra: Shortest Reach 2 | HackerRank

1. 주의할 점

- 우선순위큐를 이용한 다익스트라 알고리즘을 사용한다

- 매 TC마다 초기화를 진행한다

 

2. 구현

- 매 TC 마다 간선의 정보를 담고 있는 V[] 벡터와 각 지점까지의 거리를 저장하는 Dist[] 배열을 초기화한다

- Edges 벡터를 통해 간선의 정보를 V[] 벡터에 저장한다

- 우선순위큐를 사용한 다익스트라 알고리즘을 통해 시작점 -> 다른 Node까지의 최단거리를 Dist[]에 갱신한다

- Dist[]가 MAX 값이면 -1을, 아니면 Dist[]값 그대로 Result 벡터에 추가한다. 단, Dist[]가 0인 시작지점은 제외한다

- Result를 반환한다

#define MAX 987654321
#include <bits/stdc++.h>

using namespace std;
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val>b.val;
    }
};
info tmp;
vector<info> v[3001];
int dist[3001];
vector<string> split_string(string);

// Complete the shortestReach function below.
vector<int> shortestReach(int n, vector<vector<int>> edges, int s) {
    //초기화
    vector<int> result;
    for(int i=1;i<=n;i++){
        v[i].clear();
        dist[i]=MAX;
    }
    for(int i=0;i<edges.size();i++){
        int a = edges[i][0];
        int b = edges[i][1];
        int val = edges[i][2];
        tmp.val = val;
        tmp.idx = b;
        v[a].push_back(tmp);
        tmp.idx=a;
        v[b].push_back(tmp);
    }
    priority_queue<info,vector<info>,cmp> pq;
    tmp.idx=s;
    tmp.val=0;
    pq.push(tmp);
    dist[s]=0;
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        pq.pop();
        if(dist[cidx]<cv) continue;
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            int nv = v[cidx][i].val;
            if(dist[next]>cv+nv){
                dist[next]=cv+nv;
                tmp.val = cv+nv;
                tmp.idx = next;
                pq.push(tmp);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(i==s) continue;
        int val = (dist[i]==MAX)? -1 : dist[i];
        result.push_back(val);
    }
    return result;
}