Go to diff to previous submission
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> #include <queue> #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; #define X first #define Y second #define MP make_pair #define PB push_back #define SZ size int main () { int hodnota[1005]; int pom[1005], pom2[1005]; int hrany[1005][1005]; int sus[1005][1005]; queue<int> t; 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; } } 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) t.push(i); } while(!t.empty()) { n = t.front(); t.pop(); //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; } pom2[n] = -1; } cout << hodnota[koren] << endl; } return 0; }
--- c5.s899.cteam077.fr.cpp.0.fr.cpp +++ c5.s906.cteam077.fr.cpp.0.fr.cpp @@ -27,5 +27,4 @@ int main () { - vector<pair <int, int> > sused; int hodnota[1005]; int pom[1005], pom2[1005]; @@ -39,4 +38,5 @@ pom[i] = 0; hodnota[i] = 0; + pom2[i] = 0; } for (i = 1; i < 1002; i++) { @@ -58,8 +58,4 @@ } for (i = 1; i <= n; i++) { - sused.PB(MP(pom[i], i)); - } - sort(sused.begin(), sused.end()); - for (i = 1; i <= n; i++) { if (pom[i] == 1) t.push(i); @@ -85,5 +81,4 @@ } cout << hodnota[koren] << endl; - sused.clear(); } return 0;