floyd algorithm
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 55
const int INF = 0x3f3f3f3f;
int t, n, m, k;
int dp[N][N];
struct Edge {
int u, v, w; // 一条边所连接的两个顶点
} edges[2500];
void InitGraph() {
memset(dp, INF, sizeof dp);
for (int i = 1; i <= n; ++i) dp[i][i] = 0;
int u, v, w;
for (int i = 1; i <= m; ++i) {
scanf("%d %d %d", &u, &v, &w);
dp[u][v] = dp[v][u] = w;
edges[i] = (struct Edge) {.u = u, .v = v, .w = w};
}
}
void ReInitGraph() {
memset(dp, INF, sizeof dp);
for (int i = 1; i <= n; ++i) dp[i][i] = 0;
int u, v, w;
for (int i = 1; i <= m; ++i) {
u = edges[i].u, v = edges[i].v, w = edges[i].w;
dp[u][v] = dp[v][u] = w;
}
}
void RemoveEdge() {
int x, u, v;
while (k--) {
scanf("%d", &x);
u = edges[x].u, v = edges[x].v;
dp[u][v] = dp[v][u] = INF;
}
}
void Floyd_Algorithm() {
register int i, j, k;
for (k = 1; k <= n; ++k)
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
dp[i][j] = fmin(dp[i][j], dp[i][k] + dp[k][j]);
}
int main(void) {
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &n, &m, &k);
InitGraph();
Floyd_Algorithm();
printf("%d\n", dp[1][n] == INF ? -1 : dp[1][n]);
ReInitGraph();
RemoveEdge();
Floyd_Algorithm();
printf("%d\n", dp[1][n] == INF ? -1 : dp[1][n]);
}
return 0;
}
真有你的