[ SWEA 1803 ] Shortest Path Faster (C++)

SWExpertAcademy의 Shortest Path Faster(1803 / D4) 문제이다.

[ 문제풀이 ]

주어지는 무방향 연결그래프에서, 하나의 출발 정점에서 도착 정점에 이르는 최단거리를 구해야 하는 문제이다.

또한, 가중치가 1,000,000 이하의 양의정수로만 존재한다고 했다.

따라서 본인은 한 정점으로부터 다른 정점까지의 최단거리를 구할 수 있고, 모든 가중치가 양의 정수로만 이루어져있기 때문에

다익스트라 알고리즘을 이용해서 접근해보았다.

아직 다익스트라 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 다익스트라 알고리즘 알아보기(Click) ]

다익스트라 알고리즘만 구현할 줄 안다면, 별도의 설명이 필요 없는 문제인 것 같다.

따라서, 구체적인 설명은 위의 다익스트라 알고리즘에 대해서 설명해놓은 글로 대체하겠다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 100010
typedef long long ll;
using namespace std;
 
int N, M, Start, End;
ll Dist[MAX];
ll Answer;
vector<pair<int,int>> V[MAX];
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        V[i].clear();
        Dist[i] = 9999999999999999;
    }
}
 
void Input()
{
    cin >> N >> M >> Start >> End;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
        V[b].push_back(make_pair(a, c));
    }
}
 
void Solution()
{
    priority_queue<pair<ll, int>> Q;
    Q.push(make_pair(0, Start));
    Dist[Start] = 0;
 
    while (Q.empty() == 0)
    {
        ll Cost = -Q.top().first;
        int Cur = Q.top().second;
        Q.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            ll nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                Q.push(make_pair(-Dist[Next], Next));
            }
        }
    }
    Answer = Dist[End];
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}