ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 13.10.2021 10:26:31

ამოცანა: გრაფის დიამეტრი

მომხმარებელი: andria_beridze

ვერდიქტი: ნაწილობრივი ამოხსნა

შეფასება: 81.8 ქულა







#include<bits/stdc++.h>
#define Connect(a,b) Graph[a].push_back(b),Graph[b].push_back(a)
using namespace std;
vector<int> Graph[1005];
bool Visited[1005];
priority_queue<pair<int,int>> q;
map<pair<int, int>, int> mp;
vector<int> Ans;
void bfs(int Node) {
	q.push({ 0, Node });
	while (q.size() > 0) {
		pair<int, int> Top = q.top();
		q.pop();
		if (Visited[Top.second] == true) continue;
		Visited[Top.second] = true;
		Ans.push_back(-Top.first);
		for (int To : Graph[Top.second]) {
			q.push({ Top.first - mp[{To, Top.second}],To});
		}
	}
}
int main() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n - 1; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		Connect(a, b);
		mp[{a, b}] = w;
		mp[{b, a}] = w;
	}
	for (int i = 1; i <= n; i++) {
		if (Graph[i].size() == 1) {
			for (int i = 1; i <= n; i++) {
				Visited[i] = false;
			}
			Ans.clear();
			bfs(i);
			sort(Ans.begin(), Ans.end());
			ans = max(Ans[Ans.size() - 1], ans);
		}
	}
	cout << ans;
	return 0;
}

ტესტები

შემავალი მონაცემები
10
4 5 5
4 3 2
4 2 1
5 6 4
5 1 0
5 7 4
3 8 4
3 9 3
3 10 3
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
11 5 8
11 3 1
11 13 5
11 17 2
5 12 10
5 7 6
5 8 5
3 10 10
3 9 6
13 4 4
13 16 10
17 14 6
17 15 0
17 20 5
17 19 7
12 18 2
12 1 7
12 6 8
7 2 10
გამომავალი მონაცემები
41
თქვენი პასუხი
41
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50
44 25 3
44 15 20
44 17 17
44 20 7
25 26 15
25 14 2
15 38 19
15 10 5
17 2 10
17 31 3
17 36 18
17 45 19
17 23 2
20 7 10
20 19 18
20 3 12
20 41 19
20 6 18
26 22 18
26 48 9
14 12 14
14 30 14
38 46 17
38 4 5
38 37 4
38 40 19
38 42 ...
გამომავალი მონაცემები
113
თქვენი პასუხი
113
ჩეკერის პასუხი
YES
შემავალი მონაცემები
80
4 5 69
4 32 18
5 47 73
32 45 27
47 59 90
47 40 0
45 38 28
45 23 39
59 58 62
59 61 9
40 31 64
40 36 88
38 15 61
23 24 23
23 79 64
58 39 67
61 57 59
31 76 1
31 21 0
36 55 31
15 46 61
24 73 77
79 22 63
39 37 35
39 77 0
57 11 35
7...
გამომავალი მონაცემები
925
თქვენი პასუხი
925
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
4 96 199
4 9 168
4 51 199
96 47 197
96 26 84
9 41 48
9 54 91
9 10 138
51 63 96
51 81 74
47 40 10
47 50 119
47 73 6
26 20 139
26 19 105
41 13 139
41 39 61
41 6 35
54 11 2
54 55 171
54 12 103
10 85 63
10 46 161
63 45 183
63 37 12...
გამომავალი მონაცემები
1396
თქვენი პასუხი
1396
ჩეკერის პასუხი
YES
შემავალი მონაცემები
200
132 165 181
132 109 104
132 51 66
165 97 164
165 41 68
165 108 105
109 112 184
109 164 35
109 8 86
109 7 39
51 96 51
51 50 34
51 172 35
51 176 15
51 119 18
97 195 64
97 5 176
97 6 19
41 21 111
41 55 24
41 126 24
41 85 0
41 46 28
...
გამომავალი მონაცემები
1323
თქვენი პასუხი
1323
ჩეკერის პასუხი
YES
შემავალი მონაცემები
400
274 230 182
274 109 283
274 367 186
274 97 190
274 221 198
230 253 94
230 188 76
230 87 234
109 85 259
109 381 211
109 102 204
109 95 46
109 346 32
367 395 293
367 319 183
367 195 0
367 297 222
97 26 107
97 21 121
97 152 288
221 12...
გამომავალი მონაცემები
2099
თქვენი პასუხი
2099
ჩეკერის პასუხი
YES
შემავალი მონაცემები
500
444 243 271
444 117 66
444 67 170
444 60 88
444 109 97
243 1 142
243 203 233
243 51 94
117 340 159
117 23 288
67 227 145
67 395 46
67 71 145
67 244 164
67 320 148
67 314 242
60 130 191
60 253 55
109 155 299
109 120 246
109 426 70
...
გამომავალი მონაცემები
2070
თქვენი პასუხი
2070
ჩეკერის პასუხი
YES
შემავალი მონაცემები
600
132 286 100
132 109 31
286 112 9
286 484 327
286 93 183
286 253 389
109 388 100
109 463 186
109 3 202
109 181 129
112 102 120
112 86 77
484 172 188
484 395 241
484 519 353
484 195 1
93 497 167
253 412 41
253 455 2
253 152 260
253 1...
გამომავალი მონაცემები
3355
თქვენი პასუხი
3355
ჩეკერის პასუხი
YES
შემავალი მონაცემები
800
274 230 80
274 768 335
274 243 130
274 700 334
230 513 191
230 553 188
230 588 109
230 285 263
768 311 8
768 781 458
768 102 212
768 736 131
768 573 446
243 344 136
243 319 266
243 595 363
243 297 151
243 412 155
243 455 39
700 152 ...
გამომავალი მონაცემები
3478
თქვენი პასუხი

                    
ჩეკერის პასუხი
NO
შემავალი მონაცემები
999
832 796 277
832 841 158
832 571 93
832 871 346
832 311 400
796 876 257
796 46 266
796 728 220
796 540 483
796 40 67
796 603 190
841 63 494
841 237 178
841 296 340
841 672 28
841 807 481
841 154 471
841 594 465
571 5 120
571 412 133
...
გამომავალი მონაცემები
3671
თქვენი პასუხი

                    
ჩეკერის პასუხი
NO