#include <stdio.h>
#include <string.h>
#define N 2500
#define N_ 500
#define M (N_ * (N_ - 1) / 2)
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ej[N][N], ew[N][N], eo[N];
void append(int i, int j, int w) {
ej[i][eo[i]] = j, ew[i][eo[i]] = w, eo[i]++;
}
char visited[N]; int t, d_, w_;
int dfs(int i, int d) {
int o;
if (visited[i])
return 0;
visited[i] = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o], w = ew[i][o];
if (j == t) {
d_ = d + w, w_ = w;
return 1;
}
if (dfs(j, d + w))
return 1;
}
return 0;
}
int ii[M], jj[M], ww[M];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[hh[j]] == ww[h])
j++;
else if (ww[hh[j]] < ww[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int ds[N], rr[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, rr[i] = rr[j];
}
}
int main() {
static int dd[N], dd_[N], dd1[N], pp[N], hh[M];
int n, m, s, h, h_, i, i_, j, o, d, w, d1, w1, d2, w2;
scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
for (h = 0; h < m; h++) {
scanf("%d%d%d", &i, &j, &w), i--, j--;
append(i, j, w), append(j, i, w);
}
if (n <= N_) {
memset(dd, 0x3f, n * sizeof *dd), dd[n - 1] = 0;
memset(pp, -1, n * sizeof *pp);
memset(visited, 0, n * sizeof *visited);
while (1) {
i_ = -1;
for (i = 0; i < n; i++)
if (!visited[i] && (i_ == -1 || dd[i_] > dd[i]))
i_ = i;
if (i_ == -1)
break;
i = i_;
visited[i] = 1;
for (o = eo[i]; o--; ) {
j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (!visited[j] && dd[j] > d)
dd[j] = d, pp[j] = i;
}
}
m = 0;
for (i = 0; i < n; i++)
for (o = eo[i]; o--; ) {
j = ej[i][o], w = ew[i][o];
if (i < j && pp[i] != j && pp[j] != i)
ii[m] = i, jj[m] = j, ww[m] = dd[i] + dd[j] + w, m++;
}
for (h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
memset(dd_, 0x3f, n * sizeof *dd_);
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
rr[i] = i;
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_], w = ww[h_];
while ((i = rr[find(i)]) != (j = rr[find(j)]))
if (dd[i] > dd[j])
dd_[i] = w - dd[i], join(i, pp[i]);
else
dd_[j] = w - dd[j], join(j, pp[j]);
}
memset(dd1, 0x3f, n * sizeof *dd1), dd1[n - 1] = 0;
memset(visited, 0, n * sizeof *visited);
while (1) {
i_ = -1;
for (i = 0; i < n; i++)
if (!visited[i] && (i_ == -1 || dd1[i_] > dd1[i]))
i_ = i;
if (i_ == -1)
break;
i = i_;
visited[i] = 1;
for (o = eo[i]; o--; ) {
j = ej[i][o], w = ew[i][o], d = max(dd1[i] + w, pp[j] == i ? dd_[j] : dd[j]);
if (!visited[j])
dd1[j] = min(dd1[j], d);
}
}
printf("%d\n", dd1[0]);
} else {
visited[s] = 0, dfs(s, 0), d1 = d_, w1 = w_;
visited[s] = 0, dfs(s, 0), d2 = d_, w2 = w_;
printf("%d\n", min(max(d1, d2 + (d1 - w1) * 2), max(d2, d1 + (d2 - w2) * 2)));
}
return 0;
}
Compilation message
safest.c: In function 'main':
safest.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
safest.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d%d", &i, &j, &w), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
49744 KB |
Output is correct |
| 2 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
49756 KB |
Output is correct |
| 4 |
Correct |
8 ms |
49684 KB |
Output is correct |
