欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个 $n$ 个点 $m$ 条边构成的无重边和自环的无向连通图。
点的编号为 $1 \\sim n$。
请问:
- 从 $1$ 到 $n$ 的最短距离。
- 去掉 $k$ 条边后,从 $1$ 到 $n$ 的最短距离。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含三个整数 $n,m,k$。
接下来 $m$ 行,每行包含三个整数 $x,y,z$,表示点 $x$ 和点 $y$ 之间存在一条长度为 $z$ 的边。
最后一行包含 $k$ 个空格隔开的整数,表示去掉的边的编号。
所有边按输入顺序从 $1$ 到 $m$ 编号。
输出格式
每组数据输出占两行。
第一行输出从 $1$ 到 $n$ 的最短距离。
第二行输出去掉 $k$ 条边后,从 $1$ 到 $n$ 的最短距离。无法到达,则输出 $\-1$。
数据范围
$1 \\le T \\le 10$,
$1 \\le n \\le 50$,
$1 \\le m \\le \\frac{n(n-1)}{2}$,
$1 \\le x,y \\le n$,
$1 \\le z \\le 100$,
$1 \\le k \\le m$
输入样例:
1
4 4 1
1 2 1
2 3 1
3 4 1
1 4 1
4
输出样例:
1
3
C++ 代码
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 55, M = N * N / 2, INF = 0x3f3f3f3f;
int T, n, m, k, g[N][N], d[N][N];
pii e[M];
//floyd算法求任意两点的的最短路
int floyd()
{
memcpy(d, g, sizeof g);
for(int k = 1; k <= n; k ++)
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
if(d[1][n] == INF) return -1;
return d[1][n];
}
int main()
{
cin >> T;
while(T -- )
{
cin >> n >> m >> k;
memset(g, 0x3f, sizeof g);
for(int i = 1; i <= n; i ++) g[i][i] = 0;
for(int i = 1; i <= m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
e[i] = {a, b};
g[a][b] = g[b][a] = c;
}
cout << floyd() << endl;
while(k -- )
{
int t;
cin >> t;
int a = e[t].x, b = e[t].y;
g[a][b] = g[b][a] = INF;
}
cout << floyd() << endl;
}
return 0;
}