上海做衣服版的网站,网站搜索优化公司,零基础网站建设教学培训,wordpress for windows给定一个 n个点 m 条边构成的无重边和自环的无向连通图。 点的编号为 1∼n。 请问#xff1a;从 1到 n 的最短距离。去掉 k 条边后#xff0c;从 1 到 n的最短距离。
输入格式 第一行包含整数 T#xff0c;表示共有 T 组测试数据。每组数据第一行包含三个整数 n,m,k。接下来…给定一个 n个点 m 条边构成的无重边和自环的无向连通图。 点的编号为 1∼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≤T≤10, 1≤n≤50, 1≤m≤n(n−1)2, 1≤x,y≤n, 1≤z≤100, 1≤k≤m
输入样例 1 4 4 1 1 2 1 2 3 1 3 4 1 1 4 1 4
输出样例 1 3
#includeiostream
#includecstring
using namespace std;
const int N55,MN*N/2,INF0x3f3f3f3f;
int d[N][N],g[N][N];
int n,m,q;
struct edge{int a,b;
}e[M];
void floyd()
{memcpy(d,g,sizeof d);for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)d[i][j]min(d[i][j],d[i][k]d[k][j]);
}
int main()
{int T;cinT;while(T--){cinnmq;memset(g,0x3f,sizeof g);for(int i1;in;i) g[i][i]0;for(int i1;im;i){int a,b,c;cinabc;g[a][b]g[b][a]c;e[i].aa,e[i].bb;}floyd();coutd[1][n]endl;while(q--){int t;cint;int ae[t].a,be[t].b;g[a][b]g[b][a]INF;} floyd();if(d[1][n]INF) cout-1endl;else coutd[1][n]endl;}return 0;
}
