[LeetCode] 2642. Design Graph With Shortest Path Calculator

https://leetcode.com/problems/design-graph-with-shortest-path-calculator/description/

Design Graph With Shortest Path Calculator - LeetCode

leetcode - Design Graph With Shortest Path Calculator

문제 유형 : 다익스트라 알고리즘 / 구현

문제 난이도 : Hard

 

문제

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

Implement the Graph class:

• Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
• addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
• int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

n개의 노드가 0번부터 n-1번까지 있는 방향 가중치 그래프가 있다.

그래프의 간선은(from, to, cost)형태로 되어 있으며, 이는 from노드에서 to노드로 가는 비용이 cost인 간선을 의미합니다.

그래프 클래스를 구현하시오.

- Graph(int n, int[][] edges): 그래프를 n개의 노드로 초기화합니다. 주어진 edges들로 간선을 연결합니다.

- addEge(int[] edge): 그래프에 (from, to, cost)의  간선을 추가합니다.

- int shortestPath(int node1, int node2): node1부터 node2까지 가는데 필요한 비용의 최솟값을 구합니다. 만약 길이 없다면 -1을 반환합니다.

 

 

풀이

그래프를 만들어준다.

graph[a]에는 {{b, cost_b}, {c, cost_c}}의 형태로 담기도록 간선을 추가시키면 된다.

최단 거리 알고리즘은 다익스트라를 이용하여 목적지에 도착하게 하고, 도착하지 못하면 -1을 반환시킨다.

 

코드

C++

class Graph {
private:
    int n;
    vector<vector<pair<int, int>>> graph;
public:
    Graph(int n, vector<vector<int>>& edges) {
        this -> n = n;
        graph = vector<vector<pair<int, int>>>(n+1);

        for(const auto &edge : edges) {
            addEdge(edge);
        }
    }
    
    void addEdge(vector<int> edge) {
        int from = edge[0];
        int to = edge[1];
        int cost = edge[2];

        graph[from].push_back({to, cost});
    }
    
    int shortestPath(int node1, int node2) {
        vector<int> costs(n+1, 1e9);
        costs[node1] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({costs[node1], node1});

        while(!pq.empty()) {
            int currCost = pq.top().first;
            int currNode = pq.top().second;
            pq.pop();
            if(currNode == node2) return costs[currNode];

            for(const auto &next : graph[currNode]) {
                int nextNode = next.first;
                int nextCost = next.second;

                if(costs[nextNode] > currCost + nextCost) {
                    costs[nextNode] = currCost + nextCost;
                    pq.push({costs[nextNode], nextNode});
                }
            }
        }

        return -1;
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */