oj.uz

Submission #940830

# Submission time Handle Problem Language Result Execution time Memory
940830 2024-03-07T17:32:56 Z rainboy 가장 안전한 경로 (TOKI14_safest) C
13 / 100
 18 ms 48476 KB 
#include <stdio.h>

#define N	2500

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

int ej[N][N], ew[N][N], eo[N];

void append(int i, int j, int w) {
	ej[i][eo[i]] = j, ew[i][eo[i]] = w, eo[i]++;
}

char visited[N]; int t, d_, w_;

int dfs(int i, int d) {
	int o;

	if (visited[i])
		return 0;
	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], w = ew[i][o];

		if (j == t) {
			d_ = d + w, w_ = w;
			return 1;
		}
		if (dfs(j, d + w))
			return 1;
	}
	return 0;
}

int main() {
	int n, m, s, h, i, j, w, d1, w1, d2, w2;

	scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &i, &j, &w), i--, j--;
		append(i, j, w), append(j, i, w);
	}
	visited[s] = 0, dfs(s, 0), d1 = d_, w1 = w_;
	visited[s] = 0, dfs(s, 0), d2 = d_, w2 = w_;
	printf("%d\n", min(max(d1, d2 + (d1 - w1) * 2), max(d2, d1 + (d2 - w2) * 2)));
	return 0;
}

Compilation message

safest.c: In function 'main':
safest.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d%d%d", &n, &m, &s, &t), s--, t--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
safest.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d%d", &i, &j, &w), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48220 KB Output is correct
2 Correct 6 ms 48476 KB Output is correct
3 Correct 7 ms 48476 KB Output is correct
4 Correct 6 ms 48476 KB Output is correct