Go to diff to previous submission
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <cstring> #include <sstream> #include <stdio.h> #include <ctype.h> #include <math.h> #include <string.h> #include <stdlib.h> using namespace std; vector <int> v; vector < vector < pair<int, int> > > hrany; int bla(int koren){ //printf("Som vo vrchole: %d\n", koren+1); v[koren] = 1; int pocet_veducich = 0; int le = hrany[koren].size(); for(int i = 0; i< le; i++){ if(v[hrany[koren][i].first] == 0) pocet_veducich++; } if(pocet_veducich > 0){ int suma = 0; for(int i = 0; i< le; i++){ if(v[hrany[koren][i].first] == 0){ //printf("Idem do: %d z %d\n", hrany[koren][i].first+1, koren+1); suma += min(hrany[koren][i].second, bla(hrany[koren][i].first)); } } return suma; } else return 7000000; } int main(){ int n, koren; while(scanf("%d %d", &n, &koren) == 2){ int a,b,h; koren--; v.resize(n); for(int i = 0; i< n; i++){ v[i]=0; } hrany.resize(n); int pocet_hran = n-1; while(pocet_hran--){ scanf("%d %d %d", &a, &b, &h); a--; b--; hrany[a].push_back(make_pair(b,h)); hrany[b].push_back(make_pair(a,h)); } printf("%d\n", bla(koren)); v.clear(); hrany.clear(); } return 0; }
--- c5.s910.cteam077.fr.cpp.0.fr.cpp +++ c5.s1018.cteam077.fr.cpp.0.moj.cpp @@ -4,5 +4,4 @@ #include <vector> #include <set> -#include <queue> #include <map> #include <string> @@ -20,66 +19,72 @@ using namespace std; -#define X first -#define Y second -#define MP make_pair -#define PB push_back -#define SZ size +vector <int> v; +vector < vector < pair<int, int> > > hrany; -int main () { - int hodnota[1005]; - int pom[1005], pom2[1005]; - int hrany[1005][1005]; - int sus[1005][1005]; - queue<int> t; +int bla(int koren){ + //printf("Som vo vrchole: %d\n", koren+1); - int i, ii, n, koren, a, b, c; - while (scanf("%d %d", &n, &koren) > 0) { - for (i = 1; i < 1002; i++) { - pom[i] = 0; - hodnota[i] = 0; - pom2[i] = 0; - } - for (i = 1; i < 1002; i++) { - for (ii = 1; ii < 1002; ii++) { - hrany[i][ii] = 0; + v[koren] = 1; + int pocet_veducich = 0; + int le = hrany[koren].size(); + + for(int i = 0; i< le; i++){ + if(v[hrany[koren][i].first] == 0) pocet_veducich++; + } + + if(pocet_veducich > 0){ + int suma = 0; + + for(int i = 0; i< le; i++){ + + if(v[hrany[koren][i].first] == 0){ + //printf("Idem do: %d z %d\n", hrany[koren][i].first+1, koren+1); + suma += min(hrany[koren][i].second, bla(hrany[koren][i].first)); } + } - for (i = 0; i < n - 1; i++) { - scanf("%d %d %d", &a, &b, &c); - pom[a] = pom[a] + 1; - pom[b] = pom[b] + 1; - //cout << pom[1] << endl; - hrany[a][b] = c; - hrany[b][a] = c; - sus[a][pom[a] - 1] = b; - sus[b][pom[b] - 1] = a; - pom2[a] = pom2[a] + 1; - pom2[b] = pom2[b] + 1; - } - for (i = 1; i <= n; i++) { - if (pom[i] == 1 && i != koren) - t.push(i); - } - while(!t.empty()) { - n = t.front(); - t.pop(); + + return suma; + } + else return 7000000; +} + + + +int main(){ + + int n, koren; + while(scanf("%d %d", &n, &koren) == 2){ + int a,b,h; + koren--; - //cout << n << "aaa" << pom[1] << endl; - for (ii = 0; ii < pom[n]; ii++) { - - //cout << sus[n][ii] << "bbb" << endl; - if (hodnota[n] == 0 || hodnota[n] > hrany[n][sus[n][ii]]) - hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hrany[n][sus[n][ii]]; - else - hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hodnota[n]; - pom2[sus[n][ii]]--; - if (pom2[sus[n][ii]] == 1) - t.push(sus[n][ii]); - //cout << sus[n][ii] << " " << hodnota[sus[n][ii]] << " " << n << endl; + v.resize(n); + + for(int i = 0; i< n; i++){ + v[i]=0; } - pom2[n] = -1; - } - cout << hodnota[koren] << endl; - } + + + hrany.resize(n); + + int pocet_hran = n-1; + + while(pocet_hran--){ + scanf("%d %d %d", &a, &b, &h); + a--; + b--; + + hrany[a].push_back(make_pair(b,h)); + hrany[b].push_back(make_pair(a,h)); + + } + + + printf("%d\n", bla(koren)); + v.clear(); + hrany.clear(); + + } + return 0; }