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;
}