2019中国大学生程序设计竞赛（CCPC）---网络选拔赛-1004-path

考虑维护按照边权最小的堆，维护结点信息如下:

int u; // 上一个结点
int v; // 当前结点
LL lst; // 到上一个结点u的距离
LL now; // 到当前结点v的距离
int id; // 上一个结点u下一次需要扩展的下标

一开始，先将每个结点从最短的那条边扩展，然后对于每次操作。取队头元素，当前的路径距离就是第$idx$小的路径，用队头元素进行扩展:

1. 从结点$v$最短的一条边扩展
2. 从结点u的$id$下标编号进行扩展

扩展的时候维护上述信息。

这种贪心策略就是很对。

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
#define SZ(x) (int)(x).size()

struct Node{
    int u; // 上一个结点
    int v; // 当前结点
    LL lst; // 到上一个结点u的距离
    LL now; // 到当前结点v的距离
    int id; // 上一个结点u下一次需要扩展的下标
    bool operator<(const Node &b)const{
        return now > b.now;
    }
    void pt(){
        dbg(u)
        dbg(v)
        dbg(lst)
        dbg(now)
        dbg(id)
        dbg("----")
    }
};

typedef pair<LL, int> P;
#define w_ first 
#define v_ second
const int MAX_M = 5*1e4+100;
int Q[MAX_M], A[MAX_M];
int n,m,q;
vector<P> G[MAX_M];

void solve(){
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i) G[i].clear();
    int u,v;
    LL w;
    priority_queue<Node> que;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> w;
        G[u].push_back(make_pair(w, v));
    }
    int mxK = 0;
    for(int i = 1; i <= q; ++i){
        cin >> Q[i];
        mxK = max(mxK, Q[i]);
    }
    for(int i = 1; i <= n; ++i){
        sort(G[i].begin(), G[i].end());
        if(SZ(G[i])){ // 从G[i]最小的扩展出一条边
            P e = G[i][0];
            que.push((Node){i, e.v_, 0, e.w_, 1});
        }
    }
    int idx = 0;
    /*
    int u; // 上一个结点
    int v; // 当前结点
    LL lst; // 到上一个结点u的距离
    LL now; // 当当前结点v的距离
    int id; // 上一个结点u需要扩展的下标
    */
    while(idx < mxK){
        Node p = que.top(); 
        que.pop();
        A[++idx] = p.now;
        // 从v扩展当前结点最小的边
        if(SZ(G[p.v])) { 
            P e = G[p.v][0];
            que.push((Node){p.v, e.v_, p.now, p.now+e.w_, 1});
        }
        // 通过G[p.u][p.id]扩展
        if(p.id < SZ(G[p.u])){
            P e = G[p.u][p.id];
            que.push((Node){p.u, e.v_, p.lst, p.lst+e.w_, p.id+1});
        }
    }
    for(int i = 1; i <= q; ++i){
        cout << A[Q[i]] << endl;
    }
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}