dijkstra算法模板

原理：①https://baike.baidu.com/item/%E8%BF%AA%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/23665989

②https://blog.csdn.net/goodxin_ie/article/details/88707966

题1：得到要求路径的最小带权子图

原题：https://leetcode-cn.com/problems/minimum-weighted-subgraph-with-the-required-paths/

思路：

最短路 & 枚举

图论经典套路：枚举中间点。

记 d1[i]为从 src1 出发到达点 i的最短路，d2[i] 为从 src2 出发到达点 i 的最短路。d3[i] 为从点 i 出发到达dest的最短路（可以将原图中所有边反向，然后从 dest 出发跑 dijkstra 得到）。枚举中间点 i，答案就是 min(d1[i] + d2[i] + d3[i])。 证明

上述解法的正确性建立在这一前提上：存在一种最优路径，使得 src1 和 src2 通向 dest 的路径一旦重合就再也不会分开。上述做法其实就是在枚举公共路径中最开始的那个点。

这个前提也很容易证明。假设最优路径是 src1 -> i -> j1 -> dest 和 src2 -> i -> j2 -> dest，那么点 i即可以走到j1，也可以走到 j2。假设i -> j1 -> dest 的长度比i -> j2 -> dest更短，那 src2 -> i -> j1 -> dest 更优。故上述前提成立

class Solution {
    typedef pair<long long, int> pli;

    int n;
    //e1存储原本的有向边
    //e2存储反转的有向边
    vector<vector<int>> e1, e2;
    //v1存储原来有向边的起点
    //v2存储反转的有向边的起点
    vector<vector<int>> v1, v2;

    //dijstra算法可参考模板
    vector<long long> dijkstra(int S, vector<vector<int>> &e, vector<vector<int>> &v) {
        vector<long long> d(n);
        for (int i = 0; i < n; i++) d[i] = -1;
        priority_queue<pli> q;
        q.push(pli(0, S));
        while (!q.empty()) {
            pli p = q.top(); q.pop();
            int sn = p.second;
            long long val = -p.first;
            if (d[sn] >= 0) continue;
            d[sn] = val;
            for (int i = 0; i < e[sn].size(); i++) q.push(pli(-val - v[sn][i], e[sn][i]));
        }
        return d;
    }

public:
    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        this->n = n;
        //预处理
        e1 = e2 = v1 = v2 = vector<vector<int>>(n);
        for (auto &edge : edges) {
            e1[edge[0]].push_back(edge[1]); v1[edge[0]].push_back(edge[2]);
            e2[edge[1]].push_back(edge[0]); v2[edge[1]].push_back(edge[2]);
        }
        
        vector<long long> d1 = dijkstra(src1, e1, v1);
        vector<long long> d2 = dijkstra(src2, e1, v1);
        vector<long long> d3 = dijkstra(dest, e2, v2);
        long long ans = 1e18;
        for (int i = 0; i < n; i++) if (d1[i] >= 0 && d2[i] >= 0 && d3[i] >= 0) ans = min(ans, d1[i] + d2[i] + d3[i]);
        return ans < 1e18 ? ans : -1;
    }
};