欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-03 22:50:19
题意 "题目链接" Sol 分层图+最短路 建$k+1$层图,对于边$(u, v, w)$,首先在本层内连边权为$w$的无向边,再各向下一层对应的节点连边权为$0$的有向边 如果是取最大最小值的话可以考虑二分答案+最短路 cpp // luogu judger enable o2 // luogu ......

题意

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;
}