[Algorithm]Baekjoon 1446번 : 지름길

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

1446번: 지름길

 
 
using namespace std;
 
struct Node
{
    int dest;
    int cost;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.cost > b.cost;
    }
};
 
int n, d;
vector<vector<Node>> graph(10001);
int dist[10001] = { 0 };
 
 
int Dijkstra()
{
    priority_queue<Node, vector<Node>, cmp> pq;
    dist[0] = 0;
    pq.push({ 0,0 });
 
    while (!pq.empty())
    {
        int curPos = pq.top().dest; 
        int curCost = pq.top().cost;
        pq.pop();
 
        if (dist[curPos] < curCost) continue;
 
        for (int i = 0; i < graph[curPos].size(); ++i)
        {
            Node& nextNode = graph[curPos][i];
 
            if (curCost + nextNode.cost < dist[nextNode.dest])
            {
                dist[nextNode.dest] = curCost + nextNode.cost;
                pq.push({ nextNode.dest, dist[nextNode.dest] });
            }
        }
    }
 
    return dist[d];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> d;
 
    for (int i = 0; i <= d - 1; ++i)
    {
        graph[i].push_back({ i + 1,1 });
    }
 
    for (int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
    }
 
    memset(dist, 0x3f, sizeof(dist));
 
    cout << Dijkstra();
}
 

 

오랜만에 풀어본 다익스트라문제다. 보통 기본적인 다익스트라문제라면 간선에대한 정보가 전부 주어지지만, 이번 문제같은 경우에는 직접 간선을 만들어서 그래프에 넣어줘야 한다.

이 문제에서 주어지는 간선에 대한 정보는 듬성듬성 특정지점과 특정지점을 연결해주는거라서 그렇다.

이런 특정간선을 제외하고는 한칸이동하는데에 드는 비용은 1이니, 맨 처음에 각자 다음칸이동하는 간선을 전부 넣어준다.

이후 특정간선에 대한 간선을 넣어주고 다익스트라를 수행하면 값이 나온다.

 

이게 간선정보 주어지는게 최대 12개밖에 안주어지다보니까, 굳이 다익스트라말고 거의 완전탐색으로 푸는것도 가능하긴하다.