2019中国大学生程序设计竞赛（CCPC）—网络选拔赛-1004-path
- 2020 年 2 月 18 日
- 筆記
考虑维护按照边权最小的堆，维护结点信息如下:
int u; // 上一个结点 int v; // 当前结点 LL lst; // 到上一个结点u的距离 LL now; // 到当前结点v的距离 int id; // 上一个结点u下一次需要扩展的下标
一开始，先将每个结点从最短的那条边扩展，然后对于每次操作。取队头元素，当前的路径距离就是第$idx$小的路径，用队头元素进行扩展:
- 从结点$v$最短的一条边扩展
- 从结点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; }
