Submission details
Task:Internet connection
Sender:TuomoPera
Submission time:2020-09-26 10:33:10 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#20.01 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails
#110.01 sdetails
#12ACCEPTED0.01 sdetails
#130.01 sdetails
#14ACCEPTED0.01 sdetails
#150.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#180.01 sdetails
#190.01 sdetails
#200.01 sdetails
#210.01 sdetails
#220.01 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < nodes.size() - 1; i++) {
                    ~~^~~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
#define SIZE 1001

unsigned long long g[SIZE][SIZE] = {0};
unsigned long long c[SIZE][SIZE] = { 0 };
bool visited[SIZE] = { false };
int end_point = 0;
unsigned long long result = 0;
bool solution_found = false;
vector<int> nodes;
unsigned long long minimum = 9000000000;




void traverse(int current) {
	if (current == end_point) {

		solution_found = true;
		return;
	}
	vector<pair<int, int>> order;
	for (int i = 1; i <= end_point; i++) {
		if(g[current][i] > 0 && current != i && !visited[i])
			order.push_back(make_pair(g[current][i], i));
	}

	sort(order.rbegin(), order.rend());

	for(auto &i: order){
	//for (int i = 1; i <= end_point; i++) {
		if (g[current][i.second] > 0 && current != i.second && !visited[i.second] && !solution_found ) {
			nodes.push_back(i.second);
			if (g[current][i.second] < minimum)
				minimum = g[current][i.second];
			visited[i.second] = true;
			traverse(i.second);
			visited[i.second] = false;
			if (!solution_found)
				nodes.pop_back();
		}
	}
}

int main() {
	//freopen("cases.txt", "r", stdin);
	int num;
	cin >> end_point >> num;

	for (int i = 0; i < num; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = c;
	}
	visited[1] = true;


	bool solvable = false;
	for (int i = 0; i <= 1000; i++)
		solvable = g[i][end_point] > 0;

	if (!solvable) {
		cout << "0" << endl;
		return 0;
	}

	do {
		solution_found = false;
		nodes.push_back(1);
		traverse(1);
		if (solution_found) {
			for (int i = 0; i < nodes.size() - 1; i++) {
				g[nodes[i]][nodes[i + 1]] -= minimum;
				g[nodes[i + 1]][nodes[i]] += minimum;
				c[nodes[i]][nodes[i + 1]] += minimum;
			}
			result += minimum;
		}
		minimum = 999999999;
		nodes.clear();
	} while (solution_found);

	cout << result << endl;

	return 0;
}

Test details

Test 1

Verdict:

input
10 20
5 6 19
4 5 47
3 5 7
4 9 62
...

correct output
73

user output
0

Test 2

Verdict:

input
10 20
2 4 63
7 9 54
6 7 16
2 3 9
...

correct output
110

user output
0

Test 3

Verdict:

input
10 20
5 6 90
2 3 46
7 8 80
6 7 60
...

correct output
29

user output
0

Test 4

Verdict:

input
10 20
3 4 76
5 7 8
3 8 71
4 7 24
...

correct output
95

user output
0

Test 5

Verdict:

input
10 20
1 8 22
6 7 40
4 5 20
8 10 77
...

correct output
156

user output
0

Test 6

Verdict:

input
100 1000
63 85 864540192
22 91 974117435
64 66 953124912
85 88 6080960
...

correct output
4397669179

user output
0

Test 7

Verdict:

input
100 1000
36 93 760720873
12 75 175717522
78 79 340128710
80 83 181753465
...

correct output
5298558023

user output
0

Test 8

Verdict:

input
100 1000
20 60 909693891
55 91 570199535
21 41 118646902
37 82 824735480
...

correct output
5466229311

user output
0

Test 9

Verdict:

input
100 1000
26 44 753330451
62 67 821574279
70 95 219303983
7 44 980013084
...

correct output
4893925638

user output
0

Test 10

Verdict:

input
100 1000
15 89 501388091
50 71 396801720
15 92 324349822
29 85 184420157
...

correct output
6956499595

user output
0

Test 11

Verdict:

input
2 1
1 2 1

correct output
1

user output
0

Test 12

Verdict: ACCEPTED

input
2 1
2 1 1

correct output
0

user output
0

Test 13

Verdict:

input
2 2
1 2 1
2 1 1

correct output
1

user output
0

Test 14

Verdict: ACCEPTED

input
100 1000
1 2 539540023
2 3 244306651
3 4 253259012
3 5 630461598
...

correct output
0

user output
0

Test 15

Verdict:

input
4 5
1 2 2
1 3 5
2 4 3
3 2 2
...

correct output
4

user output
0

Test 16

Verdict: ACCEPTED

input
2 0

correct output
0

user output
0

Test 17

Verdict: ACCEPTED

input
100 0

correct output
0

user output
0

Test 18

Verdict:

input
100 196
1 2 1000000000
2 100 1000000000
1 3 1000000000
3 100 1000000000
...

correct output
98000000000

user output
0

Test 19

Verdict:

input
100 99
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
...

correct output
1000000000

user output
0

Test 20

Verdict:

input
2 2
2 1 1
1 2 1

correct output
1

user output
0

Test 21

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 3 1
2 4 1000000000
...

correct output
2000000000

user output
0

Test 22

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 4 1000000000
2 3 1
...

correct output
2000000000

user output
0