[백준] 택배 배송 (c++) 다익스트라

출처 : https://www.acmicpc.net/problem/5972

풀이 방법

평범한 다익스트라로 풀이 했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;
int n, m;
vector<vector<pair<int, int> > > graph;
int visited[50001];
int cost[50001];
const int INF = 987654321;

struct Node {
    int idx;
    int distance; 

    Node (int idx, int distance): idx(idx), distance(distance) {}

    bool operator < (const Node &n) const{
        if (distance > n.distance) return true;
        else return false;
    }
};

void dijkstra(int start) { // 시작 점에서 모든 정점에 이르는 거리 구하기
    priority_queue<Node> pq;
    pq.push(Node(start, 0)); // 자기 자신 추가하기

    while(!pq.empty()) {
        Node now = pq.top();
        visited[now.idx] = 1;
        pq.pop();
        for (int i = 0;i < graph[now.idx].size();i++) { // 이웃 탐색
            if (visited[graph[now.idx][i].first] == 1) continue;
            if (cost[graph[now.idx][i].first] > now.distance + graph[now.idx][i].second) {
                cost[graph[now.idx][i].first] = now.distance + graph[now.idx][i].second;
                pq.push(Node(graph[now.idx][i].first, cost[graph[now.idx][i].first]));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    graph.resize(n+1);
    memset(visited, 0, sizeof(visited));
    int a, b, c;
    for (int i = 0;i < m;i++) {
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    for (int i = 1;i <= n; i++) {
        cost[i] = INF;
    }

    dijkstra(1);

    cout << cost[n];
    return 0;
}