题解 | #单源最短路#

有向图就罢了，重边是什么鬼?
解法: dijkstra, 时间复杂度：O(V^2)

```
class Solution {
public:
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
// write code here
vector<vector<int>> e(n + 1, vector<int>(n + 1, INT_MAX));
vector<int> dis(n + 1, INT_MAX);
vector<bool> visit(n + 1, false);</bool></int></int></int></int>

    for (auto& g : graph) {
        e[g[0]][g[1]] = min(g[2], e[g[0]][g[1]]); // 处理重边
    }
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, minn = INT_MAX;
        for (int j = 1; j <= n; j++) {
            if (!visit[j] && dis[j] < minn) {
                minn = dis[j];
                u = j;
            }
        }
        if (u == -1) {
            break;
        }
        visit[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!visit[v] && e[u][v] != INT_MAX) {
                if (dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                }
            }
        }
    }
    return dis[n] == INT_MAX ? -1 : dis[n];
}

};
```</vector<int></vector</int>