oj.uz

Submission #471763

# Submission time Handle Problem Language Result Execution time Memory
471763 2021-09-10T18:04:52 Z rainboy Ceste (COCI17_ceste) C
64 / 160
 2500 ms 15968 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8396 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9080 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8524 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9084 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2563 ms 15968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 9316 KB Output is correct
2 Correct 1217 ms 8952 KB Output is correct
3 Execution timed out 2575 ms 9036 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2594 ms 15968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2578 ms 15948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2568 ms 15948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2592 ms 15948 KB Time limit exceeded
2 Halted 0 ms 0 KB -