[Greedy] 다익스트라 최단 경로

#include <iostream>
#include <queue>
using namespace std;

int INF = 200000000;

class Node {
public:
    int idx;
    int weight;
};

struct cmp {
    bool operator() (Node x, Node y) {
        return x.weight > y.weight;
    }
};

priority_queue<Node, vector<Node>, cmp> heap;

int nextV(bool *visited, int now) {
    int idx = -1;
    
    while (heap.size() > 0) {
        Node next = heap.top();
        heap.pop();
        if( visited[next.idx] ) continue;
        visited[next.idx] = true;
        return next.idx;
    }
    
    return idx;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int v, e, start;
    cin >> v >> e >> start;
    vector<Node> graph[v + 1];
    bool visited[v + 1];
    int result[v + 1];
    
    for (int i = 0; i <= v; i++) {
        visited[i] = false;
        result[i] = INF;
    }
    
    
    for (int i = 0; i < e; i++) {
        int num1, num2, weight;
        cin >> num1 >> num2 >> weight;
        
        Node node;
        node.idx = num2;
        node.weight = weight;
        graph[num1].push_back(node);
    }
    
    int now = start;
    result[now] = 0;
    while (now != -1) {
        int length = (int)graph[now].size();
        for (int i = 0; i < length; i++) {
            Node tempNode = graph[now][i];
            if( visited[ tempNode.idx ] ) continue;
            
            if( result[now] + tempNode.weight < result[tempNode.idx] ) {
                result[tempNode.idx] = result[now] + tempNode.weight;
                
                Node tempNode2;
                
                tempNode2.idx = tempNode.idx;
                tempNode2.weight = result[tempNode.idx];
                heap.push(tempNode2);
            }
        }
        
        now = nextV(visited, now);
    }
    
    for (int i = 1; i <= v; i++) {
        if(i > 1) cout << '\n';
        if( result[i] == INF ) cout << "INF";
        else cout << result[i];
    }
    
    
    return 0;
}

한 정점에서 다른 모든 정점까지의 최단 경로 구하기