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; }
