Submission #471761

#	Time	Username	Problem	Language	Result	Execution time	Memory
471761		rainboy	Ceste (COCI17_ceste)	C11	64 / 160	19 ms	8268 KiB

ceste

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

#define N	100
#define M	100
#define A	10000
#define INF	0x3f3f3f3f

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

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

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++)
		scanf("%d%d%d%d", &ii[h], &jj[h], &aa[h], &bb[h]), ii[h]--, jj[h]--;
	for (a = 0; a <= A; a++)
		memset(dp[a], 0x3f, n * sizeof *dp[a]);
	dp[0][0] = 0;
	for (a = 0; a <= A; a++)
		for (h = 0; h < m; h++)
			if (a + aa[h] <= A) {
				i = ii[h], j = jj[h];
				dp[a + aa[h]][j] = min(dp[a + aa[h]][j], dp[a][i] + bb[h]);
				dp[a + aa[h]][i] = min(dp[a + aa[h]][i], dp[a][j] + bb[h]);
			}
	for (i = 1; i < n; i++) {
		int ans = INF;

		for (a = 1; a <= A; a++)
			if (dp[a][i] <= ans / a)
				ans = a * dp[a][i];
		printf("%d\n", ans == INF ? -1 : ans);
	}
	return 0;
}

Compilation message (stderr)

ceste.c: In function 'main':
ceste.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
ceste.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   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