BZOJ2763: [JLOI2011]飞行路线(分层图最短路)

题意

Sol

分层图+最短路

建\(k+1\)层图，对于边\((u, v, w)\)，首先在本层内连边权为\(w\)的无向边，再各向下一层对应的节点连边权为\(0\)的有向边

如果是取最大最小值的话可以考虑二分答案+最短路

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP make_pair

#define fi first

#define se second

using namespace std;

const int MAXN = 2e5 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, M, K, S, T, TT, vis[MAXN], dis[MAXN];

vector<Pair> v[MAXN];

void AddEdge(int x, int y, int z, int f) {

    v[x].push_back(MP(y, z));

    if(f) v[y].push_back(MP(x, z));

}

void Dij(int s) {

    priority_queue<Pair> q; q.push(MP(0, s));

    memset(dis, 0x3f, sizeof(dis)); dis[s] = 0;

    while(!q.empty()) {

        if(vis[q.top().se]) {q.pop(); continue;}

        int p = q.top().se; q.pop(); vis[p] = 1;

        for(int i = 0; i < v[p].size(); i++) {

            int to = v[p][i].fi, w = v[p][i].se;

            if(dis[to] > dis[p] + w) dis[to] = dis[p] + w, q.push(MP(-dis[to], to));

        }

    }

}

int main() {

//	freopen("a.in", "r", stdin);

    N = read(); M = read(); K = read(); S = read() + 1; T = read() + 1; TT = N * (K + 1) + 1;

    for(int i = 1; i <= M; i++) {

        int u = read() + 1, v = read() + 1, w = read();

        for(int j = 0; j < K; j++) {

            AddEdge(j * N + u, j * N + v, w, 1);

            AddEdge(j * N + u, (j + 1) * N + v, 0, 0);

            AddEdge(j * N + v, (j + 1) * N + u, 0, 0);

        }

        AddEdge(N * K + u, N * K + v, w, 1);

    }

    for(int j = 0; j <= K; j++) AddEdge(j * N + T, TT, 0, 0);

    Dij(S);

    printf("%d", dis[TT]);

    return 0;

}

巴特西

BZOJ2763: [JLOI2011]飞行路线(分层图最短路)

题意

Sol

最新文章

热门文章

巴特西

BZOJ2763: [JLOI2011]飞行路线(分层图 最短路)

题意

Sol

最新文章

热门文章

BZOJ2763: [JLOI2011]飞行路线(分层图最短路)