#include <stdio.h>
#define N 1000000
#define M 1000000
#define N_ (1 << 20)
#define M_ (M * 2 + 2)
int n_, n, m, dp[N], hd[N], e[M_], Ln[M_], w[M_], ii, tt[N_ << 1];
void add(int u, int v, int w_) {
int i = ++ii;
Ln[i] = hd[u];
e[i] = v;
w[i] = w_;
hd[u] = i;
}
int ij(int i, int j) {
return dp[i] < dp[j]? i : j;
}
void pul(int i) {
tt[i] = ij(tt[i << 1], tt[i << 1 | 1]);
}
void fix(int i) {
for (i += n_; i >>= 1; ) pul(i);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d", &dp[i]), dp[i] *= -1;
for (int i = 0, u, v, w_; i < m; ++i) {
scanf("%d%d%d", &u, &v, &w_);
--u, --v;
add(u, v, w_), add(v, u, w_);
}
for (n_ = 1; n_ < n; n_ <<= 1);
dp[n] = 1;
for (int i = n; i < n_; ++i)
tt[i + n_] = n;
for (int i = 0; i < n; ++i)
tt[i + n_] = i;
for (int i = n_ - 1; i >= 1; --i)
pul(i);
for (int i_ = 0; i_ < n; ++i_) {
int u = tt[1];
tt[u + n_] = n;
fix(u);
for (int j = hd[u]; j; j = Ln[j]) {
if (dp[u] + w[j] < dp[e[j]]) {
dp[e[j]] = dp[u] + w[j];
fix(e[j]);
}
}
}
for (int i = 0; i < n; ++i)
printf("%d\n", -dp[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.c: In function 'main':
Main.c:29:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:31:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d", &dp[i]), dp[i] *= -1;
| ^~~~~~~~~~~~~~~~~~~
Main.c:34:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d%d%d", &u, &v, &w_);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |