不是VIP会员,不能显示答案

题目解答

题目:
(次短路)已知有一个n 个点m 条边的有向图G,并且给定图中的两个点s 和t,求次

短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两

行,第一行表示此段路经的长度,第二行表示此段路的一个方案



#include <cstdio>

#include <queue>

#include <utility>

#include <cstring>

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 << 1], *dis2;

int pre[maxn << 1], *pre2;

bool vis[maxn << 1];

void add(int a, int b, int c) {

++tot;

nxt[tot] = head[a];

to[tot] = b;

w[tot] = c;

head[a] = tot;

}

bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {

if (d >= dis[b])return false;

if (b < n) __(1)__ ;

q.push( __(2)__ );

dis[b] = d;

pre[b] = a;

return true;

}

void solve() {

priority_queue<pair<int, int> >q;

q.push(make_pair(0, s));

memset(dis, __(3)__ , 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))

__(4)__

} 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( __(5)__ );

}

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;

}


选择题

1) ⑴处应填( )。

2) ⑵处应填( )。

3) ⑶处应填( )。

4) ⑷处应填( )。

5) ⑸处应填( )。
考点:
分析:
解答:
评论:
老师: