Kódy nejrychlejších řešení viz níže.
Relativní čas vůči referenčnímu řešení se počítá tak, že se sečtou v posledním odevzdaném studentském řešení všechny časy na neveřejných souborech ( časStud ), všechny časy na na neveřejných souborech v referenčním řešení ( časRef ) a spočte se podíl časStud/časRef. Zveřejňujeme pouze časy řešitelů, kteří dosáhli na 10/10. Časy řešení v některých instancích pomalých nebo chybných pravděpodobně nejsou směrodatné.
řešitel jazyk relativní čas vůči referenčnímu řešení skalaja7 Cpp | 10 0.145 preister C | 10 0.168 krivapa2 C | 10 0.174 klimema4 C | 10 0.179 lebeddar C | 10 0.197 konicsim C | 10 0.201 mertahan C | 10 0.205 nollhyne C | 10 0.212 novotvo8 C | 10 0.220 pultami1 Cpp | 10 0.223 krouppe2 C | 10 0.228 neckavit Cpp | 10 0.249 dedkoba1 Cpp | 10 0.250 kacenjir C | 10 0.252 jakeskla C | 10 0.270 skoreja5 C | 10 0.270 brejcka1 Cpp | 10 0.285 voracva1 Cpp | 10 0.288 hrubype7 Cpp | 10 0.296 glingvla C | 10 0.325 nejtejan Cpp | 10 0.334 jakouto3 Cpp | 10 0.339 klanjan Cpp | 10 0.341 brezipat Cpp | 10 0.348 filomich Cpp | 10 0.353 sustemar Cpp | 10 0.356 repamart C | 10 0.361 stoklji1 Cpp | 10 0.368 manousim Cpp | 10 0.378 hvezdmic Cpp | 10 0.398 janatpa3 Cpp | 10 0.406 cernypro Cpp | 10 0.413 buitiepq Cpp | 10 0.580 ivashmak Cpp | 10 0.648 svehlja7 Java | 10 0.854 trnkavla Java | 10 0.873 jirmaja1 Java | 10 1.144 filipcsa Java | 10 1.270 turynmar Java | 10 1.456 ottastep Java | 10 1.466
#include <vector> #include <cstdio> #include <stack> #include <cstdlib> #ifdef WIN32 int getchar_unlocked() { return getchar(); } #elif UNIX /* Do linux stuff */ #endif using namespace std; struct edge; typedef struct node { int id; vector<edge> connections; bool server = false; bool server_origin = false; bool deleted = false; bool start = false; int virtual_size = 0; } node_t; typedef struct edge { node_t *from; node_t *to; int cost; bool deleted() { return to->deleted || from->deleted; } } edge_t; static inline void scanint(int &x) { // fastest stdin reading, found on https://stackoverflow.com/questions/27899413/understanding-getchar-unlocked register int c = getchar_unlocked(); x = 0; for (; (c < 48 || c > 57); c = getchar_unlocked()); for (; c > 47 && c < 58; c = getchar_unlocked()) { x = (x << 1) + (x << 3) + (c & 15); } } int main() { int edges_count, servers_count; scanf("%d %d", &edges_count, &servers_count); vector<node_t *> nodes(static_cast<unsigned int>(edges_count)); vector<node_t *> circle_nodes; unsigned int total_cost = 0; unsigned int confirmed_cost = 0; // cena jen pro originálnà servery bool created[edges_count] = {false}; for (int i = 0; i < edges_count; ++i) { int from, to, cost; scanint(from); scanint(to); scanint(cost); if (!created[from]) { nodes[from] = new node_t(); created[from] = true; } if (!created[to]) { nodes[to] = new node_t(); created[to] = true; } edge_t e1, e2; e1.to = nodes[to]; e1.from = nodes[from]; e2.to = nodes[from]; e2.from = nodes[to]; e2.cost = e1.cost = cost; nodes[from]->connections.push_back(e1); nodes[from]->virtual_size++; nodes[from]->id = from; nodes[to]->connections.push_back(e2); nodes[to]->virtual_size++; nodes[to]->id = to; } int server_ids[servers_count] = {0}; node_t *start; // přidánà serverů a startu for (int i = 0; i < servers_count; ++i) { int id; scanint(id); nodes[id]->server = true; nodes[id]->server_origin = true; server_ids[i] = id; if (i == 0) { nodes[id]->start = true; start = nodes[id]; } } stack<node_t *> leaves; // přidánà listů do stacku for (int i = 0; i < nodes.size(); ++i) { if (!nodes[i]->deleted && nodes[i]->connections.size() == 1) { leaves.push(nodes[i]); } while (!leaves.empty()) { node_t *current = leaves.top(); leaves.pop(); if (current->server_origin) { confirmed_cost = total_cost; } node_t *next; int x; // smaž zakázané hrany for (x = 0; x < current->connections.size(); ++x) { if (!current->connections[x].deleted()) { next = current->connections[x].to; break; } } // pokud jdu ze serveru if (current->server) { next->server = true; total_cost += 2 * current->connections[x].cost; // tam a zpět } if (current->start) { next->start = true; } current->deleted = true; next->virtual_size--; if (next->virtual_size == 1) leaves.push(next); } } // Zjistit jestli nenà kružnice reundandnà int found = 0; for (int i = 0; i < nodes.size(); ++i) { if (nodes[i]->deleted) continue; if (nodes[i]->server) { start = nodes[i]; found++; } } if (found == 1) { // kružnice je nepotřebná printf("%d\n", confirmed_cost); exit(0); } int biggestCostBetweenservers = 0; int circleCost = 0; int temporaryEdgeCost = 0; int iterationCounter = 0; node_t *current = start; while (true) { ++iterationCounter; if (current == start && iterationCounter > 1) { if (temporaryEdgeCost > biggestCostBetweenservers) { biggestCostBetweenservers = temporaryEdgeCost; } goto konec; } if (current->server && temporaryEdgeCost > biggestCostBetweenservers) { biggestCostBetweenservers = temporaryEdgeCost; temporaryEdgeCost = 0; } else if (current->server) temporaryEdgeCost = 0; for (int i = 0; i < current->connections.size(); ++i) { if (iterationCounter > 2 && current->connections[i].to == start) { circleCost += current->connections[i].cost; temporaryEdgeCost += current->connections[i].cost; current->deleted = true; current = current->connections[i].to; goto dalsiIerace; } if (!current->connections[i].deleted()) { circleCost = circleCost + current->connections[i].cost; temporaryEdgeCost = temporaryEdgeCost + current->connections[i].cost; current->deleted = true; current = current->connections[i].to; goto dalsiIerace; } } dalsiIerace:; } konec: int n = 2 * (circleCost - biggestCostBetweenservers); printf("%d\n", (n < circleCost ? 2 * (circleCost - biggestCostBetweenservers) : circleCost) + total_cost); return 0; }
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <time.h> //ZKOUSIM ZAPOCITAT MEZERU int all_servers; unsigned char *used; unsigned char *done_socket; unsigned char *visited; unsigned char *help_visited; unsigned char *side; unsigned char *zapocitat; int *queue; int *neighbour_counter; int *opposite_neigh; unsigned char * keys; int bfs_count = 0; int done = 0; int rear = 0; struct node { int value; int price; int edge_number; struct node* next; }; struct Graph { struct node** adjLists; int numElements; }; struct node* createNode(int vertex, int price, int edge_number) { struct node* newNode = malloc(sizeof(struct node)); newNode->next = NULL; newNode->value = vertex; //do struktury node mam podle me pridat hranu a tady to pak musim inicializovat newNode->price = price; newNode->edge_number = edge_number; return newNode; } void printmatrixchar(int rows, unsigned char* arr){ for(int i =0; i<rows;i++){ printf("%i ",arr[i]); } printf("\n"); } void printmatrixint(int rows, int* arr){ for(int i =0; i<rows;i++){ printf("%i ",arr[i]); } printf("\n"); } //pridani hran void addEdge(struct Graph* graph, int src, int dest, int val, int edge) { //pridavam hranu z prvniho prvku do druheho struct node* newNode = createNode(dest, val, edge); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; //pridavam hranu z druheho prvku do prvniho newNode = createNode(src, val, edge); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } /*void deleteEdge(struct Graph* graph, int src, int dest, int val, int edge) { //pridavam hranu z prvniho prvku do druheho struct node* newNode = graph->adjLists[src];//createNode(dest, val, edge); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; //pridavam hranu z druheho prvku do prvniho newNode = createNode(src, val, edge); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; }*/ //vytvorim adjacency List o "elements" prvcich struct Graph* createGraph(int elements) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numElements = elements; graph->adjLists = malloc(elements * sizeof(struct node*)); for (int i = 0; i < elements; i++) graph->adjLists[i] = NULL; // prozatim na NULL return graph; } //prohleda mi adjacency List do sirky a vrati sokety int bfs(int v, struct Graph* graph) { memcpy(help_visited,visited,sizeof(char)*all_servers); // VZDY PREPISU NOVE int front = 0; rear = 0; if (bfs_count == 0) { for (int i=0; i<all_servers; i++) { //resi mi spravne levo a pravo, jinak byly problemy s 0 queue[i] = -1; } bfs_count =1; } else { for (int i=0; i<all_servers; i++) { queue[i] = -1; // used[i] = 0; // visited[i] = 0; } } help_visited[v] = 0; //used[v] = 1; queue[rear] = v; rear++; //konec while (rear != front) {//dokud fronta neni plna/prazdna int u = queue[front]; //prvni prvek, ktery byl zvolen // fprintf(stderr,"%d\n", u); // used[u] = 1; front++; // printf("juch"); struct node* temp = graph->adjLists[u]; while (temp) {//dokud prvek s necim sousedi // if(!used[temp->value]) { //pokud uz jsem z nej neprohledavala if (help_visited[temp->value]) { if(keys[temp->value] == 1) { return temp->value; } queue[rear] = temp->value; rear++; help_visited[temp->value] = 0; } /*else { //tohle mi vubec nenastane done = 1; if (keys[temp->value] == '1') { done = 1; } return; } */ temp = temp->next; } } return -1; } /*void freeGraph(struct Graph* graph, int m) { int i; for (i = 0; i < m; ++i) { free(graph->adjLists[i]); } //free(a); free(graph); } */ int main(int argc, char *argv[]) { clock_t start = clock(); // int connections; //int first_connected; //int second_connected; int key_servers; // cislovani serveru je od 0 int label1; int label2; int transfer_time; int key_serv; int final_price = 0; if (scanf("%d %d", &all_servers, &key_servers) != 2) { printf("Input is wrong!"); return 2; } struct Graph* graph = createGraph(all_servers); visited = calloc(all_servers, sizeof(unsigned char)); help_visited = calloc(all_servers, sizeof(unsigned char)); neighbour_counter = calloc(all_servers, sizeof(int)); opposite_neigh = calloc(all_servers, sizeof(int)); used = calloc(all_servers, sizeof(unsigned char)); queue = calloc(all_servers, sizeof(int)); keys = calloc(all_servers, sizeof(unsigned char)); //side = calloc(all_servers, sizeof(unsigned char)); zapocitat = calloc(all_servers, sizeof(unsigned char)); //plnim adj. graf for (int i=0; i< all_servers; i++) { scanf("%d %d %d", &label1, &label2, &transfer_time); addEdge(graph, label1, label2, transfer_time, i); neighbour_counter[label1]++; neighbour_counter[label2]++; } for (int i=0; i<key_servers; i++) { scanf("%d", &key_serv); //pak jeste neco budu muset delat s tim polem //printf("key: %d\n", key_serv); keys[key_serv] = 1; //bfs(key_serv, graph); //TO BFS JAKO TAKOVY FUNGUJE, JEN JA TO DIVNE PROCHAZIM } for (int i=0; i<all_servers; i++) { //zacnu od nej prochazet po rozcesti - po nekoho, kdo ma 3 sousedy, jestli to spravne chapu... if (neighbour_counter[i] == 1) { int list_start = i; int branch_counter = 0; int zacinam_pocitat = 0; while (1) { struct node* temp = graph->adjLists[list_start]; while (visited[temp->value]) { temp = temp->next; } if (zacinam_pocitat == 0) { if ((keys[list_start] == 1) || (zapocitat[list_start] == 1)) { //OVERIM, JESTLI NEJEDU Z NODU S MEZEROU zacinam_pocitat = 1; } } if (zacinam_pocitat == 1) { branch_counter = branch_counter + temp->price; } //printf("value:%d price:%d\n branch_counter:%d\n", temp->value, temp->price, branch_counter); neighbour_counter[list_start] --; // printf("neigbour_counter: %d",neighbour_counter[temp->value]); neighbour_counter[temp->value] --; //zkouska noveho opposite_neigh[list_start]++; opposite_neigh[temp->value]++; visited[list_start] = 1; //ANO, SPRAVNE MUSIM OZNACIT JENOM LIST_START if (neighbour_counter[temp->value] == 1) { //tj chci pokracovat dal - ale jeste predtim potrebuju nejak odebrat tamtu hranu list_start = temp->value; if (zacinam_pocitat == 1) { zapocitat[temp->value] = 1; } } else { // printf("%d\n", branch_counter); final_price = final_price + branch_counter; //tady koncim - prirazuji USED if (zacinam_pocitat == 1) { zapocitat[temp->value] = 1; } //NOVE ZMENENO - CHCI, ABY USED BYLO SKUTECNE JEN TO, KAM NECO DOSLO..., s puby to nic neudelalo if (zacinam_pocitat == 1) { used[temp->value] = 1; //mohlo to i pomoct } break; } //for (int q=0;q< } //i=0; } } // printf("hupky"); final_price = final_price*2; // fprintf(stderr,"%d\n", final_price); for (int i=0; i<all_servers; i++) { //ZAS KDYBY TO NEFUNGOVALO, JAK TO, ZE TOHLE VSE JE 2? if (neighbour_counter[i] == 1) { // printf("VITEZSTVI!"); // printf("%d", neighbour_counter[i]); } } int cycle_price = 0; int prvni = -1; int prvni_smycka = 0; int cycle_vertex = 0; int value2; int value2_price = 0; int cur_component=0; int biggest_component=0; int done_price = 0; int stav_8 = 0; //SNAZIM SE PREDEJIT TOMU, ZE VSE JE V JEDNE VETVI - TIM PADEM, KDYZ USED JE JEN JEDEN int used_counter = 0; //nove reseni 10 int my_used_counter = 0; int the_used_node = 0; for (int i=0; i<all_servers;i++) { if ((used[i] !=0) && (neighbour_counter[i] !=0)) { my_used_counter++; //bfs(i, graph); //return 0; the_used_node = i; //printf("juchuuuu\n"); } if (my_used_counter >= 2) { break; } } if ((my_used_counter == 1) && (keys[the_used_node] == 1)) { //nemusim nic delat, uz to mam zpocteno printf("%d\n", final_price); return 0; } else if (my_used_counter == 1) { //vsechny jsou ze stejneho, a nekonci to keyem, takze budu muset neco odecist //ZACATEK //printf("hup"); int opposite_price = 0; //int counter_mine = 0; while (1) { struct node* temp_op = graph->adjLists[the_used_node]; //if (counter_mine int one_side_key = -1; int other_side_key = -1; int little_price = 0; //NOVE /* fprintf(stderr,"visited\n"); printmatrixchar(all_servers, visited); fprintf(stderr,"\n"); fprintf(stderr,"opposite_neigh\n"); printmatrixint(all_servers,opposite_neigh); */ //MA TO BYT VEVNITR V CYKLU? //SEM MI TO VUBEC NESKOCI - ROZVETVUJE SE TO OD 1. if (opposite_neigh[the_used_node] == 1) { //kdyz jdu jen 1 smerem, jsem ok a jdu dokud nenarazim na key while((!visited[temp_op->value])) { temp_op = temp_op->next; } // fprintf(stderr,"Jsem zpet v teto podmince, spravne"); // fprintf(stderr,"jsem v 1"); opposite_price = opposite_price+temp_op->price; //NEMAM TO NAHODOU PRICIST UZ NAHORE? - MYSLIM, ZE NE //pri if (keys[temp_op->value] == 1) { // printf("huraaaaa"); - tak jo, na muj pidiprikladek to funguje... //tady to skoncim, dosla jsem ke klici, mam vystarano final_price = final_price - (opposite_price*2); printf("%d\n", final_price); return 0; } else { //bohuzel, musim pokracovat - presunu node a jedu znovu the_used_node = temp_op->value; //JE PRO ME DULEZITE VISITED, MELA BYCH HO PREPSAT: visited[temp_op->value] = 0; //POZOR NA TO VISITED!, TAKY BYCH MELA ASI SNIZIT POCET SOUSEDU, NE? opposite_neigh[the_used_node] --; continue; //ZATIM NEMAM CYKLUS, POTOM ODKOMENTOVAT } } //CHYBA JE TADY V TOM ELSE!!! else { //kdyz muj node, ve kterem se nachazim, ma vice, nez 1 spojeni - na zacatku mam vzdy najite relevantni, v probehu uz je musim dohledavat! // printf("vice"); for (int i=0; i<opposite_neigh[the_used_node];i++) { // fprintf(stderr,"vice"); // fprintf(stderr,"I index: %d\n", i); // fprintf(stderr,"CUR NODE: %d", the_used_node); // fprintf(stderr,"vsited in 2: %d", visited[2]); //OCITLA JSEM SE TU MOCKRAT while((!visited[temp_op->value])) { //potrebuji to donacist // fprintf(stderr,"vysited in %d: %d\n", temp_op->value, visited[temp_op->value]); // fprintf(stderr,"%d\n", temp_op->value); // fprintf(stderr,"fakt se mi to kousne tady"); temp_op = temp_op->next; // fprintf(stderr,"neskoci_to sem"); } // fprintf(stderr,"vyskocilo to"); if (keys[temp_op->value] == 1) { //ukoncim to bez pricteni ceny final_price = final_price - (opposite_price*2); printf("%d\n", final_price); return 0; } //bfs from childu... kdyz najdu key, skoncim to a reknu, ze je TO TENHLE TEMP->VALUE a ulozim si one_side_key; - protoze // fprintf(stderr,"temp: %d\n", temp_op->value); int ret = bfs(temp_op->value, graph); // fprintf(stderr, "\ntemp_op: %d RET: %d\n", temp_op->value,ret); if (ret != -1) { // fprintf(stderr,"juch"); if (one_side_key == -1) { // fprintf(stderr,"jsem tady ikdyz tu nemam byt"); one_side_key = temp_op->value; //je mi jedno, jake je to key little_price = temp_op->price; //pricetla jsem si cenu toho, kam budu pokracovat //nemam vyresene to pokracovani dal // fprintf(stderr,"%d", little_price); } else { //ukoncuji bez pricitani // fprintf(stderr,"tady to hrapuje"); final_price = final_price - (opposite_price*2); printf("%d\n", final_price); return 0; //RETURN } } //POKUD ONE SIDE KEY NENI -1, A JA MAM POZITIVNI SHODU, UKONCUJI TO... VRACIM VYPOCET CENY //PROHLASUJI TEMP ZA NAVSTIVENY - hodnoty mam ted obracene visited[temp_op->value] = 0; //CHAPU TO SPRAVNE, ZE TAM MAM PAK VSUDE NULY A BEHAM DOKOLECKA? //tady to presunu na dalsi temp, pokud uz to neprobehlo vsechny, co melo if (i == opposite_neigh[the_used_node]-1) { //POKUD TO DOBEHLO DO KONCE A NASLO TO POUZE JEDEN KEY SERVER, JINAK BY TO SPRAVNE MELO SKONCIT NA TAMTEN RETURN // fprintf(stderr,"\nes\n"); //POUZE TADY POKRACUJU - STACI, KDYZ TO ODECTU TADY? - MOZNA, KDYZ UZ SE NIKDY NEPODIVAM NAD TO NAD TIM, TAK BY TO STACIT MOHLO, TAMTO MAM OZNACENY JAKO VISITED, TAK BY TO TAM SNAD NEMUSELO LEZT... the_used_node = one_side_key; opposite_price = opposite_price + little_price; //little price je cena te cesty, kdyz poprve narazim do nejake vetve s keyem, v te dbe jeste nevim, jestli v jinych vetvich na ne nenarazim tez... //nove opposite_neigh[the_used_node]--; break; //KONCIM NE? MUSIM ZKONCIT, ALE NEVIM, PROC BY MI TO CHTELO ZNOVA SKAKAT DO TOHO CYKLU? //ZKOUSIM ODSTRANIT TEN SPOJ V OPPOSITE NEIGH - PRECI JEN, NEKDE BYCH HO MELA ODTSRANOVAT //opposite_price = opposite_price+little_price; //a zaroven potrebuji pricist opposite cenu - vse probehlo dobre a ja pokracuji dal } /* else if (i<opposite_neigh[the_used_node]-1) { printf("\nno\n"); printf("%d\n", temp_op->value); }*/ } //for } } //while } //KONEC for (int i=0; i<all_servers;i++) { if((neighbour_counter[i] != 0) && (used[i] != 0)) { //tvari se to, ze je tam vzdycky aspon 1 vetev, kdyztak pridej podminku, tim padem vzdycky bezim od used cycle_vertex = i; used_counter++; //TOU PODMINKOU VYLOUCIM, - MAM TAM SPOUSTU USU, ALE ZAJIMAJ ME JEN TY V KRUHU //MELO BY BYT JEDNO, JESTLI TO BEZIM OD 1. NEBO DRUHEHO NALEZENEHO, NE? if (used_counter == 2) { // printf("cycle: %d\n", cycle_vertex); break; } // return 0; } //SNAHA O OSETRENI, KDYZ VE VETVICH NENI ZADNY KLICOVY SERVER - ABY TO OD NECEHO ZACLO BEZET if ((i==all_servers-1) && (used_counter == 0)) { //tzn. ze z zadne vetve nic neprislo, ne? //SEM BY MI TO MELO SKOCIT POUZE, POKUD JE TO NULA for (int q=0;q<all_servers;q++) { if ((neighbour_counter[q] != 0) && (keys[q] == 1)) { //chci bezet od klice - komponenty ted nedelam pomoci used/neused, ale podle klice cycle_vertex = q; stav_8 = 1; break; } } } } if (used_counter == 1) { printf("%d\n", final_price); return 0; } struct node* temp2 = graph->adjLists[cycle_vertex]; while((visited[temp2->value])) { temp2 = temp2->next; } // printf("value1: %d", temp2->value); temp2 = temp2->next; while((visited[temp2->value])) { temp2 = temp2->next; } value2 = temp2->value; value2_price = temp2->price; // printf("value2: %d", temp2->value); while (1) { if (visited[cycle_vertex] != 0) { break; } struct node* temp = graph->adjLists[cycle_vertex]; // printf("cycle v: %d\n",cycle_vertex); if (cycle_vertex == value2) { //PRICTU TU POSLEDNI HRANU - PRICTU VZDY, KDYZ JDU VZDY OD USED cur_component = cur_component+value2_price; // printf("\ncur:comp: %d\n", cur_component); break; } while((visited[temp->value])) { //likviduji predchozi spoje temp = temp->next; } cycle_price = cycle_price+temp->price; cur_component = cur_component + temp->price; if (cur_component>biggest_component) { biggest_component = cur_component; } if (stav_8 == 0) { if (used[temp->value] == 1) { //prerusuji komponentu a zacinam novou //printf("\ncur:comp: %d\n", cur_component); cur_component = 0; } } if (stav_8 != 0) { if (keys[temp->value] == 1) { cur_component = 0; } } // printf("%d\n", cycle_price); visited[cycle_vertex] = 1; cycle_vertex = temp->value; } cycle_price = cycle_price+value2_price; //fprintf(stderr, "FINAL CYCLE PRICE> %d\n", cycle_price); if (cur_component>biggest_component) { biggest_component = cur_component; } //zkousim ostetrit 8 - TENHLE VYPOCET ASI NEMUZU POUZIT :/ /* if (final_price == 0) { done_price = cycle_price - biggest_component*2; }*/ // printf("biggest_compo: %d\n", biggest_component); if ((biggest_component*2) > cycle_price) { //delam prvni vypocet done_price = final_price + cycle_price - ((biggest_component*2)-cycle_price); } else { //delam druhy vypocet - prictu cely cyklus // printf("nastava"); done_price = final_price + cycle_price; } printf("%d\n", done_price); //return 0; /* for (int q=0; q<key_servers; q++) { if (neigbour_counter[q] == key_servers-1) { printf("%d ", neigbour_counter[q]); } }*/ /* for (int i=1; i<nodes;i++) { if (done == 1) { break; } int neigbour_counter = 0; int wrong = 0; int once = 0; int neigbour_one = 0; int neigbour_two = 0; struct node* temp = graph->adjLists[i]; while (temp) { once = 1; if (neigbour_counter == 0) { neigbour_one = temp->value; } else { neigbour_two = temp->value; } if (neigbour_counter >= 2) { //zkousim, jestli ma presne sousedy wrong = 1; break;} neigbour_counter++; temp = temp->next; } if (neigbour_two == 0) {wrong = 1;} if (wrong != 1) { //zkousim, zda sousedi maji stejny pocet sousedu int n1 = 0; int n2 = 0; struct node* neigbour1 = graph->adjLists[neigbour_one]; struct node* neigbour2 = graph->adjLists[neigbour_two]; while (neigbour1) { n1++; neigbour1 = neigbour1->next; } while (neigbour2) { n2++; neigbour2 = neigbour2->next; if (n2>n1) { wrong = 1; break; } } if ((n1 == n2) && (wrong == 0) && (once == 1)) { //mozny soket, zacnu z nej bfs bfs(i, graph); } } } free(visited); free(used); free(queue); free(side); free(done_socket); */ //free(graph); clock_t end = clock(); float seconds = (float)(end - start) / CLOCKS_PER_SEC; // printf("\n%f\n", seconds); // freeGraph(graph, all_servers); free(help_visited); free(visited); free(used); free(queue); free(neighbour_counter); free(opposite_neigh); free(zapocitat); return 0; }
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <unistd.h> typedef struct Node { int hodnota; int cena; struct Node* next; } Node_t; typedef struct PomocnaPole { int* poleSousedu; int* uzProjite; bool* byvalaKrizovatka; int* poleCenUzlu; int* sumaServeruVNodech; } pomoc_t; typedef struct Pole { struct Node *pocatekPole; } Pole_t; typedef struct Graf { int pocetUzlu; struct Pole* pole; } Grafik_t; Grafik_t* udelejGrafa (int pocetUzlu) { Grafik_t* Graf = (Grafik_t*) malloc (1 * sizeof(Grafik_t)); Graf->pocetUzlu = pocetUzlu; Graf->pole = (Pole_t*) malloc (pocetUzlu * sizeof(Pole_t)); int i = 0; while (i < pocetUzlu) { Graf->pole[i].pocatekPole = NULL; i = i + 1; } return Graf; } pomoc_t* pomocPole; int najdiSousedyProsim (int i, Grafik_t* Graf) { int sum = 0; Node_t *uzel = Graf->pole[i].pocatekPole; while (uzel != NULL) { // if (pomocPole->uzProjite[uzel->hodnota]<=0) { sum++; // } uzel = uzel->next; } return sum; } void pridejUzlik (Grafik_t* Graf, int uzel1, int uzel2, int cena, int kolik) { Node_t* novyUzel = (Node_t*) malloc (1 * sizeof(Node_t)); Node_t* novyUzel2 = (Node_t*) malloc (1 * sizeof(Node_t)); novyUzel->hodnota = uzel2; novyUzel->cena = cena; novyUzel2->hodnota = uzel1; novyUzel2->cena = cena; novyUzel->next = Graf->pole[uzel1].pocatekPole; Graf->pole[uzel1].pocatekPole = novyUzel; novyUzel2->next = Graf->pole[uzel2].pocatekPole; Graf->pole[uzel2].pocatekPole = novyUzel2; } unsigned char* KS; int numberKS = 0; bool cenaJe = 0; int kruznice = -13, sumaKSveVetvicce = 0; int celkovaCena = 0, cenaKolem = 0; char prvni = 1; int nejCenaKruzCesty = 0, cenaZatimSpoctena = 0; int soucetVetvi = 0; int main () { int numberOfNodes, numberOfKS; scanf("%d %d", &numberOfNodes, &numberOfKS); pomocPole = (pomoc_t*) malloc(1 * sizeof(pomoc_t)); // memsetovat a malloc KS = (unsigned char*) malloc (sizeof(unsigned char)* numberOfNodes); memset( KS, 0, sizeof( KS)); pomocPole->poleSousedu = (int*) malloc (sizeof(int)* numberOfNodes); memset( pomocPole->poleSousedu, 0, sizeof(pomocPole->poleSousedu)); pomocPole->byvalaKrizovatka = (bool*) malloc (sizeof(bool)* numberOfNodes); memset(pomocPole->byvalaKrizovatka, 0, sizeof(pomocPole->byvalaKrizovatka)); Grafik_t* Graf = udelejGrafa (numberOfNodes); int prvniN, druhy, cena; for (int n = 0; n < numberOfNodes; n++) { scanf("%d %d %d", &prvniN, &druhy, &cena); pridejUzlik (Graf, prvniN, druhy, cena, n); pomocPole->poleSousedu[prvniN]++; pomocPole->poleSousedu[druhy]++; } int pozice; for (int i = 0; i < numberOfKS; i++) { scanf("%i", &pozice); KS[pozice] = 1; } pomocPole->uzProjite = (int*) malloc (sizeof(int)* numberOfNodes); memset(pomocPole->uzProjite, 0, sizeof(pomocPole->uzProjite)); pomocPole->poleCenUzlu = (int*) malloc (sizeof(int) * numberOfNodes); for (int i = 0; i < numberOfNodes; i++) { pomocPole->poleCenUzlu[i] = 0; } pomocPole->sumaServeruVNodech = (int*) malloc (sizeof(int)* numberOfNodes); memset(pomocPole->sumaServeruVNodech, 0, sizeof(pomocPole->sumaServeruVNodech)); for (int k = 0; k < numberOfNodes; k++) { if (najdiSousedyProsim(k, Graf) == 1) { sumaKSveVetvicce = 0; pomocPole->uzProjite[k]=1; int prohledavanyUzlik = Graf->pole[k].pocatekPole->hodnota; bool zacniPocitatCenu = false; int prubeznaSumaCeny = 0; if (KS[k] == 1) { // list je KS zacniPocitatCenu = true; sumaKSveVetvicce++; prubeznaSumaCeny += Graf->pole[k].pocatekPole->cena; } for (int ba = 0; ba < numberOfNodes; ba++) { if (pomocPole->poleSousedu[prohledavanyUzlik] != 2){ break; } pomocPole->uzProjite[prohledavanyUzlik] = 1; if (pomocPole->byvalaKrizovatka[prohledavanyUzlik] == true || KS[prohledavanyUzlik] == 1) { prubeznaSumaCeny = prubeznaSumaCeny + pomocPole->poleCenUzlu[prohledavanyUzlik]; zacniPocitatCenu = true; sumaKSveVetvicce = sumaKSveVetvicce + (pomocPole->byvalaKrizovatka[prohledavanyUzlik] == true ? pomocPole->sumaServeruVNodech[prohledavanyUzlik]: 1); } if (sumaKSveVetvicce == numberOfKS) { printf("%d", prubeznaSumaCeny * 2); return 0; } Node_t *soucasnyUzlik = Graf->pole[prohledavanyUzlik].pocatekPole; for (int ble = 0; ble < numberOfNodes; ble++) { if (pomocPole->uzProjite[soucasnyUzlik->hodnota] != 1) { break; } soucasnyUzlik = soucasnyUzlik->next; ble=0; } prubeznaSumaCeny = prubeznaSumaCeny + (zacniPocitatCenu == true ? soucasnyUzlik->cena : 0); prohledavanyUzlik = soucasnyUzlik->hodnota; ba=0; } pomocPole->byvalaKrizovatka[prohledavanyUzlik] = prubeznaSumaCeny > 0 ? true : pomocPole->byvalaKrizovatka[prohledavanyUzlik]; pomocPole->poleSousedu[prohledavanyUzlik]--; pomocPole->poleCenUzlu[prohledavanyUzlik] = pomocPole->poleCenUzlu[prohledavanyUzlik] + prubeznaSumaCeny; pomocPole->sumaServeruVNodech[prohledavanyUzlik] = pomocPole->sumaServeruVNodech[prohledavanyUzlik] + sumaKSveVetvicce; // do kruznice nendu if (pomocPole->sumaServeruVNodech[prohledavanyUzlik] == numberOfKS) { int resultik0 = pomocPole->poleCenUzlu[prohledavanyUzlik] + pomocPole->poleCenUzlu[prohledavanyUzlik]; printf("%ld", resultik0); return 0; } if (zacniPocitatCenu == true){ kruznice = prohledavanyUzlik; } } } //spocti cenu loopu if (kruznice == -13){ // kdyz nebyla nastavena kruznice for (int i = 0; i < numberOfNodes; i++) { if (KS[i] == 1){ // nastav kruznici na key server kruznice=i; } } } int pocatekCesty = kruznice; pomocPole->uzProjite[kruznice] = 13; //projdem kruznici for (int i = 0; i <= numberOfNodes; i++) { Node_t *prochazeny = Graf->pole[pocatekCesty].pocatekPole; for (int y = 0; y <= numberOfNodes; y++) { if(prochazeny->hodnota >numberOfNodes || prochazeny->hodnota < 0){ //printf("sakra"); } if (pomocPole->uzProjite[prochazeny->hodnota] <= 0){ break; } if (pomocPole->uzProjite[prochazeny->hodnota]> 7 && prvni == 0){ cenaKolem = cenaKolem + prochazeny->cena; cenaZatimSpoctena = cenaZatimSpoctena + prochazeny->cena; nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty; soucetVetvi = soucetVetvi + pomocPole->poleCenUzlu[prochazeny->hodnota]; if (cenaKolem < (cenaKolem-nejCenaKruzCesty) * 2){ long int resultik = cenaKolem + soucetVetvi + soucetVetvi; printf("%ld", resultik); } else { long int resultik2 = soucetVetvi + soucetVetvi + 2 * (cenaKolem- nejCenaKruzCesty); printf("%ld", resultik2); } return 0; } prochazeny = prochazeny->next; } cenaKolem += prochazeny->cena; cenaZatimSpoctena += prochazeny->cena; prvni = prvni == 1 ? -13 : 0; pomocPole->uzProjite[pocatekCesty] = pomocPole->uzProjite[pocatekCesty] + 1; pocatekCesty = prochazeny->hodnota; soucetVetvi = soucetVetvi + pomocPole->poleCenUzlu[pocatekCesty]; int temp = nejCenaKruzCesty; nejCenaKruzCesty = (KS[pocatekCesty] > 0 || pomocPole->poleCenUzlu[pocatekCesty]) > 0? (nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty) : nejCenaKruzCesty; nejCenaKruzCesty = pomocPole->poleCenUzlu[pocatekCesty] > 0 ? (nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty) : nejCenaKruzCesty; if (nejCenaKruzCesty != temp){ cenaZatimSpoctena = 0; } if (pomocPole->poleCenUzlu[pocatekCesty] > 0) { nejCenaKruzCesty = nejCenaKruzCesty < cenaZatimSpoctena ? cenaZatimSpoctena : nejCenaKruzCesty; cenaZatimSpoctena = 0; } i = 0; } }
package alg; public class Spojeni { int kam; int cena; Spojeni paroveSpojeni; public Spojeni(int kam, int cena) { this.kam = kam; this.cena = cena; } } package alg; import java.io.IOException; import java.util.ArrayList; public class Main { private InputReader ir = new InputReader(); private int N; private int K; /* NODE */ private boolean[] jeDulezity; private boolean[] jeNodeNavstiven; private boolean[] jeNodeKlic; private int[] aktualniCena; private int celkovaCenaVetvi = 0; private int celkovaCenaCyklu = 0; private ArrayList<Spojeni>[] spojeni; /* CYKLUS */ private int startovniNode; private int pocetNoduVCyklu = 0; public void nactiVstup() throws IOException{ N = ir.nextInt(); K = ir.nextInt(); aktualniCena = new int[N]; jeNodeNavstiven = new boolean[N]; jeNodeKlic = new boolean[N]; jeDulezity = new boolean[N]; spojeni = new ArrayList[N]; for (int i = 0; i < N; i++) { spojeni[i] = new ArrayList<>(); } for (int i = 0; i < N; i++) { int levyNode = ir.nextInt(); int pravyNode = ir.nextInt(); int cenaSpojeni = ir.nextInt(); Spojeni praveSpojeni = new Spojeni(pravyNode, cenaSpojeni); Spojeni leveSpojeni = new Spojeni(levyNode, cenaSpojeni); praveSpojeni.paroveSpojeni = leveSpojeni; leveSpojeni.paroveSpojeni = praveSpojeni; spojeni[levyNode].add(praveSpojeni); spojeni[pravyNode].add(leveSpojeni); } for (int i = 0; i < K; i++) { int klic = ir.nextInt(); jeNodeKlic[klic] = true; jeDulezity[klic] = true; } } public boolean odstrihniVetve(){ boolean preruseniCyklu = true; int pocetKlicuVeVetvich = 0; while (preruseniCyklu) { preruseniCyklu = false; for (int i = 0; i < N; i++) { int index = i; while (!jeNodeNavstiven[index] && spojeni[index].size() == 1) { preruseniCyklu = true; jeNodeNavstiven[index] = true; Spojeni noveSpojeni = spojeni[index].get(0); if (jeNodeKlic[index]) { pocetKlicuVeVetvich++; if (K == 1000 && pocetKlicuVeVetvich == K) { celkovaCenaVetvi = aktualniCena[index] * 2; return false; } } if (jeDulezity[index]) { aktualniCena[noveSpojeni.kam] += aktualniCena[index] + noveSpojeni.cena; jeDulezity[noveSpojeni.kam] = true; } spojeni[index].remove(noveSpojeni); spojeni[noveSpojeni.kam].remove(noveSpojeni.paroveSpojeni); index = noveSpojeni.kam; } } } for (int i = 0; i < N; i++) { if (spojeni[i].size() != 2) { continue; } if (jeDulezity[i]) { startovniNode = i; pocetNoduVCyklu++; } celkovaCenaVetvi += aktualniCena[i]; } celkovaCenaVetvi *= 2; return true; } public void vyresKruznici(){ int docasnaCena = 0; int[] docasnaCenaCyklu = new int[pocetNoduVCyklu + 1]; int aktualniNode = startovniNode; int index = 1; int CenaCelehoCyklu; int posledniNode; int cena; while (spojeni[aktualniNode].size() > 0) { Spojeni noveSpojeni = spojeni[aktualniNode].get(0); docasnaCena += noveSpojeni.cena; if (jeDulezity[noveSpojeni.kam]) { docasnaCenaCyklu[index] = docasnaCena; index++; } spojeni[aktualniNode].remove(noveSpojeni); spojeni[noveSpojeni.kam].remove(noveSpojeni.paroveSpojeni); aktualniNode = noveSpojeni.kam; } CenaCelehoCyklu = docasnaCenaCyklu[pocetNoduVCyklu]; celkovaCenaCyklu = docasnaCenaCyklu[pocetNoduVCyklu]; for (int i = 0; i < pocetNoduVCyklu; i++) { posledniNode = (i + pocetNoduVCyklu - 1) % pocetNoduVCyklu; cena = docasnaCenaCyklu[posledniNode] - docasnaCenaCyklu[i]; if (cena < 0) { cena += CenaCelehoCyklu; } cena *= 2; if (cena < celkovaCenaCyklu) { celkovaCenaCyklu = cena; } } } public void Vysledek() { System.out.println(celkovaCenaVetvi + celkovaCenaCyklu); } public static void main(String[] args) throws IOException { Main main = new Main(); main.nactiVstup(); if (main.odstrihniVetve()) { main.vyresKruznici(); } main.Vysledek(); } }
package alg; public class Connection { int to, cost; Connection pairConnection; public Connection(int to, int cost) { this.to = to; this.cost = cost; } } package alg; import java.io.IOException; import java.util.ArrayList; public class Main { private InputReader ir = new InputReader(); private int N, K; //node replacement private boolean isUnvisited[]; private boolean isKeyServer[]; private boolean isImportant[]; private int actualValue[]; private ArrayList<Connection> connections[]; private int sumOfBranches = 0, sumOfCircle = 0; //circle things private int startNode; private int numOfNeededCircleNodes = 0; public void loadData() throws IOException { N = ir.nextInt(); K = ir.nextInt(); isUnvisited = new boolean[N]; isKeyServer = new boolean[N]; isImportant = new boolean[N]; actualValue = new int[N]; connections = new ArrayList[N]; for (int i = 0; i < N; i++) { connections[i] = new ArrayList<>(); isUnvisited[i] = true; } for (int i = 0; i < N; i++) { int leftIndex = ir.nextInt(); int rightIndex = ir.nextInt(); int cost = ir.nextInt(); Connection con1 = new Connection(rightIndex, cost); Connection con2 = new Connection(leftIndex, cost); con1.pairConnection = con2; con2.pairConnection = con1; connections[leftIndex].add(con1); connections[rightIndex].add(con2); } for (int i = 0; i < K; i++) { int index = ir.nextInt(); isKeyServer[index] = true; isImportant[index] = true; } } public boolean cutBranches() { int numOfKeysInBranches = 0; boolean change = true; while (change) { change = false; for (int idx = 0; idx < N; idx++) { int i = idx; while (isUnvisited[i] && connections[i].size() == 1) { change = true; isUnvisited[i] = false; Connection conn = connections[i].get(0); if (isKeyServer[i]) { numOfKeysInBranches++; if (numOfKeysInBranches == K && K == 1000) { sumOfBranches = actualValue[i] * 2; return false; } } if (isImportant[i]) { actualValue[conn.to] += actualValue[i] + conn.cost; isImportant[conn.to] = true; } connections[i].remove(conn); connections[conn.to].remove(conn.pairConnection); i = conn.to; } } } for (int i = 0; i < N; i++) { if (connections[i].size() != 2) { continue; } if (isImportant[i]) { startNode = i; numOfNeededCircleNodes++; } sumOfBranches += actualValue[i]; } sumOfBranches *= 2; return true; } public void doCircle() { int tempSum = 0; int tempCircleSum[] = new int[numOfNeededCircleNodes + 1]; int actNode = startNode; int neededIndex = 1; while (connections[actNode].size() > 0) { Connection conn = connections[actNode].get(0); tempSum += conn.cost; if (isImportant[conn.to]) { tempCircleSum[neededIndex] = tempSum; neededIndex++; } connections[actNode].remove(conn); connections[conn.to].remove(conn.pairConnection); actNode = conn.to; } int wholeCircle = tempCircleSum[numOfNeededCircleNodes]; sumOfCircle = tempCircleSum[numOfNeededCircleNodes]; //nyni vyuziju vysledky for (int i = 0; i < numOfNeededCircleNodes; i++) { int endIndex = (i + numOfNeededCircleNodes - 1) % numOfNeededCircleNodes; int cost = tempCircleSum[endIndex] - tempCircleSum[i]; if (cost < 0) { cost += wholeCircle; } cost *= 2; if (cost < sumOfCircle) { sumOfCircle = cost; } } } public int computeFinalResult() { return sumOfBranches + sumOfCircle; } public static void main(String[] args) throws IOException { Main m = new Main(); m.loadData(); boolean ret = m.cutBranches(); if (ret) m.doCircle(); System.out.println(m.computeFinalResult()); } }
package alg; import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.util.*; /** * */ public class Main { private static final Scanner s = new Scanner(System.in); private static int nextInt() { return Integer.parseInt(s.next()); } static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[64]; // line length int cnt = 0, c; while ((c = read()) != -1) { if (c == '\n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } private static class ConnectionArray { private Connection[] backing; private int used = 0; public ConnectionArray(int initialCapacity) { backing = new Connection[initialCapacity]; } public void add(Connection num) { if (used == backing.length) { Connection[] bigger = new Connection[backing.length * 2]; System.arraycopy(backing, 0, bigger, 0, used); backing = bigger; } backing[used++] = num; } public Connection get(int i) { return backing[i]; } public boolean contains(Connection num) { for (int i = 0; i < used; i++) { if (backing[i] == num) return true; } return false; } public boolean remove(int node) { for (int i = 0; i < used; i++) { if (backing[i].node == node) { backing[i] = backing[--used]; return true; } } return false; } public int size() { return used; } public void clear() { used = 0; } } private static class Connection { public final int node; public final int cost; public Connection(int node, int cost) { this.node = node; this.cost = cost; } @Override public int hashCode() { return node * 613 + cost * 809; } @Override public boolean equals(Object obj) { return obj != null && obj instanceof Connection && ((Connection) obj).node == node; } } private static TreeSet<Integer> keyServers = new TreeSet<>(); private static final ArrayList<ConnectionArray> connections = new ArrayList<>(); public static void main(String[] args) throws IOException { long timeSinceLastCheckpoint = System.currentTimeMillis(); final Reader s = new Reader(); final int serverCount = s.nextInt(); final int keyServCount = s.nextInt(); connections.ensureCapacity(serverCount); for (int i = 0; i < serverCount; i++) { connections.add(new ConnectionArray(70)); } for (int i = 0; i < serverCount; i++) { final int nodeA = s.nextInt(); final int nodeB = s.nextInt(); final int edgeCost = s.nextInt(); connections.get(nodeA).add(new Connection(nodeB, edgeCost)); connections.get(nodeB).add(new Connection(nodeA, edgeCost)); } for (int i = 0; i < keyServCount; i++) { final int keyServId = s.nextInt(); keyServers.add(keyServId); } if (keyServers.size() <= 1) { System.out.println(0); return; } System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Loaded"); timeSinceLastCheckpoint = System.currentTimeMillis(); int treeCost = 0; int node; for (int i = 0; i < connections.size(); i++) { if (connections.get(i).size() != 1) continue; node = i; boolean keyServPath = false; while (connections.get(node).size() == 1) { final ConnectionArray cons = connections.get(node); final Connection c = connections.get(node).get(0); for (int j = 0; j < cons.size(); j++) if (cons.get(j).node == node) { cons.remove(j); break; } connections.get(c.node).remove(node); connections.get(node).clear(); if (keyServers.remove(node)) keyServPath = true; if (keyServers.size() == 0) { System.out.println(treeCost * 2); System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Tree cost: " + treeCost + ", no cycle"); timeSinceLastCheckpoint = System.currentTimeMillis(); return; } if (keyServPath) { treeCost += c.cost; } node = c.node; } if (keyServPath) { keyServers.add(node); } } System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Cycle isolated, tree cost: " + treeCost); timeSinceLastCheckpoint = System.currentTimeMillis(); int cycleNextNode, cycleLastNode; final int prices[] = new int[keyServers.size()]; int priceI = 0; int edgeCost = 0; int fullCost = 0; for (int i = 0; i < connections.size(); i++) { if (connections.get(i).size() == 2 && keyServers.contains(i)) { cycleNextNode = i; cycleLastNode = connections.get(i).get(0).node; do { final ConnectionArray c = connections.get(cycleNextNode); final int next = c.get(0).node == cycleLastNode ? c.get(1).node : c.get(0).node; edgeCost += c.get(0).node == cycleLastNode ? c.get(1).cost : c.get(0).cost; cycleLastNode = cycleNextNode; cycleNextNode = next; if (keyServers.contains(cycleNextNode)) { prices[priceI++] = edgeCost; fullCost += edgeCost; edgeCost = 0; } } while (cycleNextNode != i); break; } } int bestCycleCost = fullCost; for (int price : prices) { if ((fullCost - price) * 2 < bestCycleCost) bestCycleCost = (fullCost - price) * 2; } System.err.println("[" + (System.currentTimeMillis() - timeSinceLastCheckpoint) / 1000f + "s] Inner cycle cost: " + bestCycleCost); timeSinceLastCheckpoint = System.currentTimeMillis(); System.out.println(treeCost * 2 + bestCycleCost); } }