hdu path 6705 最短路
发布时间:2020-12-14 05:08:46 所属栏目:大数据 来源:网络整理
导读:题意 ?输出所有路径的第k短路 ? 队友放入优先队列一个个搜 ?时间复杂度没问题 ?但是MLE了 ? 可以用set维护 #includebits/stdc++.h #define pi pairint,int #define mk make_pair #define ll long long using namespace std; const int maxn = 5e4 + 10 ; str
题意 ?输出所有路径的第k短路 ? 队友放入优先队列一个个搜 ?时间复杂度没问题 ?但是MLE了 ? 可以用set维护 #include<bits/stdc++.h> #define pi pair<int,int> #define mk make_pair #define ll long long using namespace std; const int maxn = 5e4 + 10; struct node { int u; ll dis; bool operator<(const node& t) const { return dis > t.dis; } }; vector<pi> G[maxn]; priority_queue<node> q; multiset<ll> s; ll ans[maxn * 10]; int qry[maxn]; void init(int n) { s.clear(); for (int i = 1; i <= n; i++) G[i].clear(); while (!q.empty()) q.pop(); } int main() { int T; scanf("%d",&T); while (T--) { int n,m,Q,u,v,w,k,mx = 0; scanf("%d%d%d",&n,&m,&Q); for (int i = 1; i <= m; i++) { scanf("%d%d%d",&u,&v,&w); G[u].push_back(mk(w,v)); q.push(node{v,w}); s.insert(w); } for (int i = 1; i <= n; i++) sort(G[i].begin(),G[i].end()); for (int i = 1; i <= Q; i++) scanf("%d",&qry[i]),mx = max(mx,qry[i]); int cnt = 0; while (cnt < mx) { node tmp = q.top(); q.pop(); ans[++cnt] = tmp.dis; if (cnt >= mx) break; u = tmp.u; for (auto it : G[u]) { v = it.second; ll w = it.first + tmp.dis; if (s.size() == mx) { auto cat = --s.end(); if (w >= *cat) break; s.erase(cat); s.insert(w); } else s.insert(w); q.push(node{v,w}); } } for (int i = 1; i <= Q; i++) printf("%lldn",ans[qry[i]]); init(n); } } ? 参考大佬 :https://blog.csdn.net/ccsu_cat/article/details/100047649 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |