const auto& [disu,u] = pq.top() 使不得!!!!

P4768

spfa的墓碑

#include<bits/stdc++.h>
using namespace std;
#define int unsigned
using pii = pair<unsigned, unsigned>;
using cint = const int&;
constexpr int maxn = 200010, maxm = 400010, maxlg = 20;
struct { int nxt, v, w; }edge[maxm << 1];
struct { int u, v, a; }e[maxm];
int maxlgn, T, p, s, n, m, q, u, v, l, a, dis[maxn << 1], head[maxn], fa[maxlg + 1][maxn << 1], dat[maxn], ecnt, * ht;
inline void addedge(cint u, cint v, cint w) {
    edge[++ecnt] = { .nxt = head[u],.v = v,.w = w };
    head[u] = ecnt;
}
bool k, vis[maxn];
namespace dsu {
    int fa[maxn << 1];
    inline void init(cint n) { for (int i = 1; i <= n; ++i)fa[i] = i; }
    int getfa(cint x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
}
inline void dijkstra(cint s) {
    memset(dis + 1, 0x3f3f3f, sizeof(dis[0]) * n);
    memset(vis + 1, 0, n);
    static priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({ dis[s] = 0,s });
    while (!pq.empty()) {
        const auto [disu, u] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto i = head[u]; i; i = edge[i].nxt)
            if (const auto v = edge[i].v, w = edge[i].w; dis[v] > disu + w)
                pq.push({ dis[v] = disu + w,v });
    }
}
inline void krust() {
    int cnt = n;
    ht = dat - n;
    dsu::init(n << 1);
    sort(e + 1, e + m + 1, [](const auto& a, const auto& b) {return a.a > b.a; });
    for (int i = 1; i <= m && cnt < (n << 1); ++i) {
        const auto ufa = dsu::getfa(e[i].u), vfa = dsu::getfa(e[i].v);
        if (ufa == vfa) continue;
        dsu::fa[ufa] = dsu::fa[vfa] = fa[0][ufa] = fa[0][vfa] = ++cnt;
        ht[cnt] = e[i].a;
        (dis[cnt] = min(dis[vfa], dis[ufa]));
    }
    for (int i = 1; i <= maxlgn; ++i)
        for (int j = 1; j <= (n << 1); ++j)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
}
inline int get(int u, cint p) {
    for (int i = maxlgn; i + 1 > 0; --i)
        if (fa[i][u] && ht[fa[i][u]] > p) u = fa[i][u];
    return dis[u];
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--) {
        ecnt = maxlgn = 0;
        cin >> n >> m;
        while (n >> maxlgn) ++maxlgn;
        memset(head + 1, 0, sizeof(head[0]) * n);
        for (int i = 0; i <= maxlgn; ++i) memset(fa[i] + 1, 0, sizeof(fa[0][0]) * n);
        for (int i = 1; i <= m; ++i) {
            cin >> e[i].u >> e[i].v >> l >> e[i].a;
            addedge(e[i].u, e[i].v, l);
            addedge(e[i].v, e[i].u, l);
        }
        dijkstra(1);
        krust();
        cin >> q >> k >> s;
        int lastans = 0;
        while (q--) {
            cin >> v >> p;
            v = (v + k * lastans - 1) % n + 1;
            p = (p + k * lastans) % (s + 1);
            cout << (lastans = get(v, p)) << '\n';
        }
    }
}

简单且显然
可惜了有一段非常重要的东西:

//Line 26
const auto [disu, u] = pq.top();
const auto& [disu, u] = pq.top();//寄!引用top,寄!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇