Submission #1197037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197037		sleepntsheep	Treasure Hunt (CCO24_day1problem1)	C11	25 / 25	607 ms	50036 KiB

Main

#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;
}

Compilation message (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_);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8