阅读程序（2） 6-10题 组合题 次短路。已知有一个n个点m条边的有向图G，并且给定图中的两个点s和t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示此段路经的长度，第二行表示此段路的一个方案。 #include #include #include #include using namespace std; const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279; int n, m, s, t; int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1; int dis[maxn > &q) { if (d >= dis[b])return false; if (b >q; q.push(make_pair(0, s)); memset(dis, ( ③ ), sizeof(dis)); memset(pre, -1, sizeof(pre)); dis2 = dis + n; pre2 = pre + n; dis[s] = 0; while (!q.empty()) { int aa = q.top().second; q.pop(); if (vis[aa])continue; vis[aa] = true; int a = aa % n; for (int e = head[a]; e; e = nxt[e]) { int b = to[e], c = w[e]; if (aa < n) { if (!upd(a, b, dis[a] + c, q)) ( ④ ); } else { upd(n + a, n + b, dis2[a] + c, q); } } } } void out(int a) { if (a != s) { if (a < n) out(pre[a]); else out( ⑤ ); } printf("%d%c", a % n + 1, " \n"[a == n + t]); } int main() { scanf("%d%d%d%d", &n, &m,&s,&t); s--, t--; for (int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a - 1, b - 1, c); } solve(); if (dis2[t] == inf) puts("-1"); else { printf("%d\n", dis2[t]); out(n + t); } return 0; }
正确答案：完善程序①答案：dis[b+n]=d（b<n时同步更新次短路点b+n）。核心：次短路初始化。
试卷来源：2024 CSP-S提高级（第一轮）C++真题