MENU

洛谷P4568/BZOJ2763/洛谷P2939/BZOJ1579 [JLOI2011]飞行路线/[USACO09FEB]Revamping Trails

洛谷P4568

BZOJ2763

洛谷P2939

BZOJ1579

分层图最短路模板,层内正常连边,层间连0边。

#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
#include<functional>
#include<cstring>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
using namespace std;
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T = int>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd(), m = ip.rd(), k = ip.rd(), s = ip.rd(), t = ip.rd(), dis[100000];
vector<pair<int, int>> e[100000];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main() {
    int a, b, c;
    while (m--) {
        a = ip.rd(), b = ip.rd(), c = ip.rd();
        e[a].emplace_back(b, c), e[b].emplace_back(a, c);
        for (int j = 1; j <= k; ++j)e[a + (j - 1) * n].emplace_back(b + j * n, 0), e[b + (j - 1) * n].emplace_back(a + j * n, 0), e[a + j * n].emplace_back(b + j * n, c), e[b + j * n].emplace_back(a + j * n, c);
    }
    for (int i = 1; i <= k; ++i) e[t + (i - 1) * n].emplace_back(t + i * n, 0);
    memset(dis, 0x7f, sizeof dis), dis[s] = 0, pq.emplace(0, s);
    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();
        if (t.first != dis[t.second])continue;
        for (auto v : e[t.second]) {
            if (dis[v.first] <= dis[t.second] + v.second)continue;
            dis[v.first] = dis[t.second] + v.second, pq.emplace(dis[v.first], v.first);
        }
    }
    ip.print(dis[t + k * n]);
}
Tags: None
Leave a Comment

captcha
请输入验证码