blob: 38ad94720cafb12782c8f32cb5c895537155ba42 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
// 2492. Minimum Score of a Path Between Two Cities
#include <limits.h>
#include <math.h>
#include <stdlib.h>
int find_father(int **u, int val) {
int k = val;
while (k != u[k][0])
k = u[k][0];
return k;
}
int minScore(int n, int **roads, int roads_size, int *roads_col_size) {
int **u = malloc((n + 1) * sizeof(int *));
for (int i = 1; i <= n; i++) {
u[i] = malloc(3 * sizeof(int));
u[i][0] = i;
u[i][1] = 1;
u[i][2] = INT_MAX;
}
for (int i = 0; i < roads_size; i++) {
int a = find_father(u, roads[i][0]);
int b = find_father(u, roads[i][1]);
int min = fmin(roads[i][2], fmin(u[a][2], u[b][2]));
if (a == b) {
u[a][2] = min;
continue;
}
if (u[a][1] >= u[b][1]) {
u[b][0] = a;
u[a][2] = min;
u[a][1] += u[b][1];
} else {
u[a][0] = b;
u[b][2] = min;
u[b][1] += u[a][1];
}
}
int first = find_father(u, 1), last = find_father(u, n), ans;
if (first != last)
ans = -1;
else
ans = u[first][2];
for (int i = 1; i <= n; i++)
free(u[i]);
free(u);
return ans;
}
|