最短路径

6032. 得到要求路径的最小带权子图

dijsktra模版

    typedef long long ll;
    typedef pair<int, int> pll;
    struct edge {
        int to, cost;//目的点序号，权重
    };
    vector<ll> dijkstra(int s, int n, vector<vector<edge>> &S) {
        vector<ll> dist(n, INF);
        dist[s] = 0;
        priority_queue<pll, vector<pll>, greater<pll> > pque;
        pque.push({0, s});//分别存储 距离，节点编号
        while(!pque.empty()) {
            auto p = pque.top(); pque.pop();//取出目前离源点距离最短的点v
            ll v = p.second, d = p.first;//v是该点序号，d是该点到源点距离
            if(dist[v] < d) continue;//如果当前到该点的最短距离比之前记录的短，跳过
            for (auto &e : S[v]) {//对点v的连接边更新
                if(dist[e.to] > dist[v] + e.cost) {
                //如果v某一连接点到源点的最短路径 > v到源点的最短路径+v到该点路径权值
                //难么就替换值，并把该连接点pair入堆
                    dist[e.to] = dist[v] + e.cost;
                    pque.push({dist[e.to], e.to});
                }
            }
        }
        return dist;
    }