题意
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606407.html