Submission #471763

#	Time	Username	Problem	Language	Result	Execution time	Memory
471763		rainboy	Ceste (COCI17_ceste)	C11	64 / 160	2594 ms	15968 KiB

ceste

#include <stdio.h>
#include <string.h>

#define N	2000
#define M	2000
#define A	2000
#define INF	0x3f3f3f3f
#define LINF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

int main() {
	static int dp[A + 1][N], ii[M], jj[M], aa[M], bb[M];
	static long long ans[N];
	int n, m, h, i, j, a, a_, a1;

	scanf("%d%d", &n, &m);
	a_ = 0;
	for (h = 0; h < m; h++) {
		scanf("%d%d%d%d", &ii[h], &jj[h], &aa[h], &bb[h]), ii[h]--, jj[h]--;
		a_ += aa[h];
	}
	for (a = 0; a <= A; a++)
		memset(dp[a], 0x3f, n * sizeof *dp[a]);
	memset(ans, 0x3f, n * sizeof *ans);
	dp[0][0] = 0;
	for (a = 0; a <= a_; a++) {
		for (h = 0; h < m; h++) {
			i = ii[h], j = jj[h];
			a1 = (a + aa[h]) % (A + 1);
			dp[a1][j] = min(dp[a1][j], dp[a % (A + 1)][i] + bb[h]);
			dp[a1][i] = min(dp[a1][i], dp[a % (A + 1)][j] + bb[h]);
		}
		for (i = 0; i < n; i++)
			if (dp[a % (A + 1)][i] != INF)
				ans[i] = min(ans[i], (long long) dp[a % (A + 1)][i] * a), dp[a % (A + 1)][i] = INF;
	}
	for (i = 1; i < n; i++)
		printf("%lld\n", ans[i] == LINF ? -1 : ans[i]);
	return 0;
}

Compilation message (stderr)

ceste.c: In function 'main':
ceste.c:17:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
ceste.c:20:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d%d%d%d", &ii[h], &jj[h], &aa[h], &bb[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16