# 2642. Design Graph With Shortest Path Calculator
## 想法
使用Floyd-Warshall algorithm

## 程式碼

#define ll long long
#define inf (ll)1e15
class Graph {
public:
    vector <vector<ll>> dis;
    int n;
    Graph(int n, vector<vector<int>>& edges) {
        this -> n = n;
        dis.resize(n, vector<ll>(n, inf));
        for (int i = 0; i < n; i++) {
            dis[i][i] = 0;
        }
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            dis[u][v] = w;
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }
    
    void addEdge(vector<int> edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (w >= dis[u][v]) return;
        dis[u][v] = w;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][u] + w + dis[v][j]);
            }
        }

    }
    
    int shortestPath(int node1, int node2) {
        if (dis[node1][node2] == inf) return -1; 
        return dis[node1][node2];
    }
};

/**
 * 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);
 */

## 想法
使用 Dijkstra's algorithm
## 程式碼

#define oo 1e9
class Graph {
public:
    vector<vector<pair<int,int>>> adj;
    int n;
    Graph(int n, vector<vector<int>>& edges) {
        this->n = n;
        adj.resize(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            adj[u].push_back({v, w});
        }
    }
    
    void addEdge(vector<int> edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        adj[u].push_back({v, w});
    }
    
    int shortestPath(int node1, int node2) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> dis(n, oo);
        vector<bool> done(n);
        dis[node1] = 0;
        pq.push({0, node1});
        while (!pq.empty()) {
            auto [step, u] = pq.top();
            pq.pop();
            if (done[u]) continue;
            done[u] = 1;
            for (auto [v, w] : adj[u]) {
                if (step + w < dis[v]) {
                    dis[v] = step + w;
                    pq.push({dis[v], v});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (dis[i] == oo) {
                dis[i] = -1;
            }
        }
        return dis[node2];
    }
};

/**
 * 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);
 */