fr.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct EDGE
{
int u;
int v;
int w;
}
EDGE;
typedef struct FOL
{
int v;
int w;
}
FOL;
EDGE Input[4000];
int Degree[4000];
FOL Fol[4000];
int iFol[4000];
int CurIndex[4000];
int Pred[4000];
int Q[4000];
int QBeg, QEnd;
int wPred[4000];
int Cost[4000];
int MyMin(int a, int b)
{
return (a < b) ? a : b;
}
int main()
{
int n, c;
while(scanf("%d%d", &n, &c) > 0)
{
c--;
memset(Degree, 0, sizeof(Degree));
memset(CurIndex, 0, sizeof(CurIndex));
memset(Cost, 0, sizeof(Cost));
int m = n - 1;
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &(Input[i].u), &(Input[i].v), &(Input[i].w));
Input[i].u--;
Input[i].v--;
Input[i + m].u = Input[i].v;
Input[i + m].v = Input[i].u;
Input[i + m].w = Input[i].w;
Degree[Input[i].u]++;
Degree[Input[i].v]++;
}
iFol[0] = 0;
for(int i = 0; i < n; i++)
{
iFol[i + 1] = iFol[i] + Degree[i];
}
int mm = m * 2;
for(int i = 0; i < mm; i++)
{
int e = Input[i].u;
Fol[iFol[e] + CurIndex[e]++] = (FOL) {Input[i].v, Input[i].w};
}
//seznam nasledniku hotov
/*for(int i = 0; i < mm; i++)
{
printf("%d->%d with %d\n", Input[i].u + 1, Input[i].v + 1, Input[i].w);
}*/
Pred[c] = -1;
QBeg = 0;
QEnd = 0;
Q[QEnd++] = c;
while(QBeg < QEnd)
{
int cur = Q[QBeg++];
for(int i = iFol[cur]; i < iFol[cur + 1]; i++)
{
int t = Fol[i].v;
if(t == Pred[cur])
{
continue;
}
Pred[t] = cur;
wPred[t] = Fol[i].w;
Q[QEnd++] = t;
}
}
//Pred inicializovan
QBeg = 0;
QEnd = 0;
for(int i = 0; i < n; i++)
{
if((i != c) && (Degree[i] == 1))
{
Q[QEnd++] = i;
Cost[i] = 1 << 30;
}
}
while(QBeg < QEnd)
{
int cur = Q[QBeg++];
int pred = Pred[cur];
Cost[pred] += MyMin(Cost[cur], wPred[cur]);
//printf("Cost of %d increased by min(%d, %d)\n", pred + 1, Cost[cur], wPred[cur]);
if(pred != c)
{
if(--Degree[pred] == 1)
{
Q[QEnd++] = pred;
}
}
}
//Cost inicializovan
printf("%d\n", Cost[c]);
}
return 0;
}