阅读程序:
#include <cstdio> const int N = 5010; const int M = 20010; const int inf = 1073741823; int e, bg[N], nx[M], to[M], wt[M]; inline void link(int u, int v, int w) { to[++e] = v; nx[e] = bg[u]; wt[e] = w; bg[u] = e; } int n, m, u, v, w; int f[N], h[N << 1]; void update(int x, int y) { x += n - 1; for (h[x] = y; x; x >>= 1) h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1]; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i != m; ++i) { scanf("%d%d%d", &u, &v, &w); link(u, v, w); } int nn = n << 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j != nn; ++j) h[j] = 0; for (int j = 0; j <= n; ++j) f[j] = inf; f[i] = 0; update(i, i); for (int j = i; true; j = h[1]) { if (f[j] == inf) break; for (int k = bg[j]; k; k = nx[k]) { if (f[j] + wt[k] < f[to[k]]) { f[to[k]] = f[j] + wt[k]; update(to[k], to[k]); } } update(j, 0); } for (int j = 1; j <= n; ++j) printf("%d%c", f[j], "\n "[j != n]); } return 0; }
以下程序的输入是一张带边权的有向图,完成下面的判断题和单选题:
将程序中所有的 “!=” 替换为 “<”,程序将仍然正常运行且输出的结果不会改变。 ( )
为了保证程序正常运行,输入的边数必须不大于 2 × 104。 ( )
程序的输出是一个 n×n 的整数矩阵。 ( )
将程序第 34 行的 “j=0” 替换为 “j=1”,程序将仍然正常运行且输 出的结果不会改变。 ( )
当输入的图中所有边的边权均为一个相同的正整数,且有∑ 𝑤𝑖 < 1073741823 时,“update” 函数被调用的次数为( )。
Θ(𝑛2)
Θ(𝑛𝑚)
Θ(𝑛2 + 𝑛𝑚)
Θ(𝑛min(𝑛,𝑚))
当输入的边权均为正整数时,程序在最坏情况下的时间复杂度为( )。
Θ(𝑛3)。
Θ(𝑛2 log 𝑛 + 𝑛𝑚)。
Θ(𝑛𝑚 log 𝑛)。
Θ(𝑛2𝑚)。