题意 输出所有路径的第 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("%lld\n", ans[qry[i]]);
- init(n);
- }
- }
- View Code
参考大佬 :https://blog.csdn.net/ccsu_cat/article/details/100047649
来源: http://www.bubuko.com/infodetail-3169758.html