2019ccpc网络赛hdu6705 path

怼烎@ 2023-08-17 17:21 62阅读 0赞

# path #

[题目传送门][Link 1]

## 解题思路 ##

先用vector存图，然后将每个vector按照边的权值从小到大排序。将每个顶点作为起点的边里最短的边存入优先队列。对于存入优先队列的信息，应有边起点，终点，是其起点的第几短边，以及路径总长度。优先队列按照路径长度从小到大排序，每次出队当前最短的路径，对于一条路径，更新两条新的可能最短的路径，即这条路后面加上一条可走的最短边，以及这条路最后一条边换成一条次短边。将询问排序，不断更新答案即可。

## 代码如下 ##

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 100010; struct T{ int x, y, f; ll w; T(int x, int y, ll w, int f): x(x), y(y), w(w), f(f){} bool operator<(const T& a)const{ return w > a.w; } }; struct line{ int r; ll w; line(int r, ll w): r(r), w(w){} bool operator<(const line& a)const{ return w < a.w; } }; vector<line> vec[N]; struct R{ int i, k; bool operator<(const R& a)const{ return k < a.k; } }qy[N]; ll ans[N]; priority_queue<T> pq; int main() { int t; scanf("%d", &t); while(t --){ int n, m, q; scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= m; i ++){ int u, v; ll w; scanf("%d%d%lld", &u, &v, &w); vec[u].push_back(line(v, w)); } for(int i = 1; i <= n; i ++){ sort(vec[i].begin(), vec[i].end()); } for(int i = 1; i <= n; i ++){ if(vec[i].size()) pq.push(T(i, vec[i][0].r, vec[i][0].w, 0)); } for(int i = 1; i <= q; i ++){ scanf("%d", &qy[i].k); qy[i].i = i; } sort(qy + 1, qy + q + 1); int cnt = 0; int id = 1; while(!pq.empty()){ int x = pq.top().x; int y = pq.top().y; ll w = pq.top().w; int f = pq.top().f; pq.pop(); ++cnt; while(id <= q && cnt == qy[id].k){ ans[qy[id].i] = w; ++id; } if(id > q) break; if(vec[y].size()) pq.push(T(y, vec[y][0].r, w + vec[y][0].w, 0)); if(vec[x].size() > f + 1) pq.push(T(x, vec[x][f + 1].r, w + vec[x][f + 1].w - vec[x][f].w, f + 1)); } for(int i = 1; i <= q; i ++){ printf("%lld\n", ans[i]); } for(int i = 0; i <= n; i ++) vec[i].clear(); while(!pq.empty()) pq.pop(); } return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11403890.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6705