传送门 这道题讲的是两个人去旅行，然后他们会在一个地方（不是两者的起点）碰头，并且最后还要回到各自的起点，然后有 k k k 张免费的机票，求总的价值以及他们可能会碰头的其中一个点。
由于有 k k k 张免费的机票，并且难以模拟在哪一趟兑换这张免费机票，所以采用拆边的做法，将一段路拆分成 k + 1 k+1 k+1 段，第一段表示需要付费的票，后面分别表示使用第一张免费票的路线，第二张…第 k k k 张
这里后面回到起点的做法，直接在原来给出的建图的基础上建立反边即可，便把起点当作源点，按部就班的跑一遍 d i j k s t r a dijkstra dijkstra 即可
此题还有个坑点就是，在路线较少的时候， k k k 张免费的机票可能用不完，需要去对这 k k k 张票就是枚举
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> pll; template <typename T> inline void rd(T& x) { ll tmp = 1; char c = getchar(); x = 0; while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } x *= tmp; } const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int N = 1e4 + 1; const int M = 1e6 + 10; const double eps = 1e-8; struct edge { int next, to, w; }e1[M], e2[M]; int head1[N*11], head2[N*11], cnt1, cnt2; void add(edge e[], int head[], int& cnt, int u, int v, int w) { e[cnt].to = v; e[cnt].next = head[u]; e[cnt].w = w; head[u] = cnt++; } int n, m, a, b, k; int id[N][11]; ll dis1[N*11], dis2[N*11], dis3[N*11], dis4[N*11]; bool vis[N*11]; struct node { int v; ll len; bool friend operator<(const node& a, const node& b) { return a.len > b.len; } node(int v, ll len) :v(v), len(len) {} }; void dijkstra(edge e[], int head[], int& cnt, ll dis[], int st) { for (int i = 0; i < N * 11; ++i) dis[i] = 1e16; dis[st] = 0; memset(vis, false, sizeof vis); priority_queue<node>que; que.push(node(st, 0)); while (!que.empty()) { node vn = que.top(); que.pop(); if (vis[vn.v]) continue; int u = vn.v; vis[u] = true; dis[u] = vn.len; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (vis[v]) continue; que.push(node(v, vn.len + e[i].w)); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // FILE* _INPUT = freopen("input.txt", "r", stdin); // FILE* _OUTPUT = freopen("output.txt", "w", stdout); memset(head1, -1, sizeof head1); memset(head2, -1, sizeof head2); cnt1 = cnt2 = 0; rd(n), rd(m), rd(a), rd(b), rd(k); int num = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= k; ++j) { id[i][j] = ++num; } } while (m--) { int u, v, w; rd(u), rd(v),rd(w); for (int j = 0; j < k; ++j) { add(e1, head1, cnt1, id[u][j], id[v][j], w); add(e1, head1, cnt1, id[u][j], id[v][j + 1], 0); add(e2, head2, cnt2, id[v][j], id[u][j], w); add(e2, head2, cnt2, id[v][j], id[u][j + 1], 0); } add(e1, head1, cnt1, id[u][k], id[v][k], w); add(e2, head2, cnt2, id[v][k], id[u][k], w); } dijkstra(e1, head1, cnt1, dis1, id[a][0]); dijkstra(e1, head1, cnt1, dis2, id[b][0]); dijkstra(e2, head2, cnt2, dis3, id[a][0]); dijkstra(e2, head2, cnt2, dis4, id[b][0]); int pos = -1; ll ans = 1e16; for (int i = 0; i < n; ++i) { if (a == i || b == i) continue; ll ans1 = 1e16, ans2 = 1e16; for (int j1 = 0; j1 <= k; ++j1) { for (int j2 = 0; j2 <= k - j1; ++j2) { int v1 = id[i][j1]; int v2 = id[i][j2]; if (ans1 > dis1[v1] + dis3[v2]) { ans1 = dis1[v1] + dis3[v2]; } if (ans2 > dis2[v1] + dis4[v2]) { ans2 = dis2[v1] + dis4[v2]; } } } if (ans > ans1 + ans2) { ans = ans1 + ans2; pos = i; } } if (ans == 1e16) puts(">:("); else printf("%d %lld\n", pos, ans); return 0; }