fr.cpp
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int traverse(int node, bool *visited, int **mat, int n) {
visited[node] = true;
int total = 0;
for (int i = 0; i < n; i++) {
if (!visited[i] && mat[node][i]) {
int sub = traverse(i, visited, mat, n);
total += sub && sub < mat[node][i] ? sub : mat[node][i];
}
}
return total;
}
int main() {
int nn, nc;
scanf("%d %d", &nn, &nc);
bool quit = false;
while (!quit) {
int n = nn;
int c = nc;
// prepare
int **mat = new int *[n];
int *matInner = new int[n*n];
memset(matInner, 0, n*n*sizeof(int));
for (int i = 0; i < n; i++)
mat[i] = matInner+i*n;
// read edges
int u, v, w;
while (scanf("%d %d", &u, &v) == 2) {
if (getchar() == '\n') {
nn = u;
nc = v;
goto CMPT;
}
scanf("%d", &w);
// use edge u, v, w
u--, v--;
mat[u][v] = mat[v][u] = w;
}
quit = true;
CMPT:
// compute here
c--;
bool *visited = new bool[n];
memset(visited, 0, n*sizeof(bool));
int result = traverse(c, visited, mat, n);
printf("%d\n", result);
// dealloc
delete [] mat;
delete [] matInner;
}
return 0;
}