Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <utility> #include <string> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; /* 3 1 2 1 5 1 3 4 */ //#define debug printf #define debug blackhole void blackhole(...) {} #define MAXN 1005 int ADJACENT[MAXN][MAXN]; int ADJACENT_W[MAXN][MAXN]; int ADJ_N[MAXN]; long COST[MAXN]; int V; /* long RECURSE(long FROM_W, long FROM_V, int v) { long ss = 0; if (ADJ_N[v] == 1 && FROM_V == -1) { return ADJACENT_W[v][0]; // jedina hrana z korenu } if (ADJ_N[v] == 1) { return FROM_W; // list } for (int i = 0; i < ADJ_N[v]; i++) { if (ADJACENT[v][i] == FROM_V) continue; ss += RECURSE(ADJACENT_W[v][i], v, ADJACENT[v][i]); } if (FROM_W != -1 && FROM_W < ss) ss = FROM_W; return ss; } */ /* long FROM_WS[10000], FROM_VS[10000], VS[10000], IS[10000], RESULT; long STACKSIZE=0; void RECURSE() { long FROM_W=FROM_WS[STACKSIZE], FROM_V=FROM_VS[STACKSIZE], v=VS[STACKSIZE]; if (ADJ_N[v] == 1) return FROM_W; for (int i = 0; i < ADJ_N[v]; i++) { if (ADJACENT[v][i] == FROM_V) continue; ss += RECURSE(ADJACENT_W[v][i], v, ADJACENT[v][i]); if (FROM_W != -1 && FROM_W < ss) { ss = FROM_W; break; } } if (FROM_W != -1 && FROM_W < ss) ss = FROM_W; return ss; } */ int KOR = -1; void DESTROY_ALL_BELOW(int v) { if (COST[v] != -1) return; if (ADJ_N[v] == 1 && v != KOR) { COST[v] = ADJACENT_W[v][0]; debug("list(%d): cost=%d\n", v, ADJACENT_W[v][0]); return; } long SUM = 0; long PATH_UP = -1; for (int i = 0; i < ADJ_N[v]; i++) { if (COST[ADJACENT[v][i]] != -1) { SUM += COST[ADJACENT[v][i]]; } else { debug("Path up of %d: vertex %d\n", v, ADJACENT[v][i]); if (PATH_UP != -1) { printf("ERR"); exit(2); } PATH_UP = ADJACENT_W[v][i]; } } debug("path up=%ld sum=%ld\n", PATH_UP, SUM); long Q = -1; if (PATH_UP == -1 || SUM < PATH_UP) Q = SUM; else Q = PATH_UP; debug("COST[%d]<-%ld\n", v, Q); COST[v] = Q; } long QUEUE[MAXN]; long QZ = 0; long QL = 0; void GO() { if (KOR==-1) { printf("ERROR!!!\n"); exit(1); } debug("KOR=%d\n",KOR); for (int i=0;i<MAXN;i++) { ADJ_N[i]=0; COST[i] = -1; } for (int i = 0; i < V - 1; i++) { int a, b, weight; scanf("%d%d%d", &a, &b, &weight); //printf("%d %d %d\n", a,b,weight); //printf("%d %d\n", ADJ_N[a], ADJ_N[b]); ADJACENT[a][ADJ_N[a]] = b; ADJACENT_W[a][ADJ_N[a]] = weight; ADJ_N[a]++; ADJACENT[b][ADJ_N[b]] = a; ADJACENT_W[b][ADJ_N[b]] = weight; ADJ_N[b]++; } QZ=0; QL=0; for (int i = 0; i < V + 1; i++) { if (ADJ_N[i] == 1 && i != KOR) { QUEUE[QL++] = i; debug("LIST: %d\n", i); } } while (QZ<QL) { DESTROY_ALL_BELOW(QUEUE[QZ]); for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) { if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) { int p=ADJACENT[QUEUE[QZ]][i]; int pocet=0; for (int j =0;j<ADJ_N[p];j++) { if(COST[ADJACENT[p][j]]==-1) pocet++; } if (pocet==1 && p !=KOR) QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i]; if (pocet==0) QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i]; } } QZ++; } printf("%ld\n", COST[KOR]); // printf("%ld\n", RECURSE(-1, -1, KOR)); } int main() { while (true) { if (scanf("%d%d", &V, &KOR) != 2) break; GO(); } return 0; }
--- c5.s620.cteam032.fr.cpp.0.fr.cpp +++ c5.s710.cteam032.fr.cpp.0.fr.cpp @@ -124,4 +124,5 @@ QZ=0; + QL=0; for (int i = 0; i < V + 1; i++) { if (ADJ_N[i] == 1 && i != KOR) { @@ -135,5 +136,14 @@ for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) { if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) { - QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i]; + int p=ADJACENT[QUEUE[QZ]][i]; + int pocet=0; + for (int j =0;j<ADJ_N[p];j++) { + if(COST[ADJACENT[p][j]]==-1) + pocet++; + } + if (pocet==1 && p !=KOR) + QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i]; + if (pocet==0) + QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i]; } }