|
|
back to boardWhy WA on TEST#1 SOS SOS~~~~~~~~ I don't know why it WAs on #1. I think my algorithm should work. The following is my code. Thinks in advance. #include <stdio.h> #include <stdlib.h> #include <math.h> void main() { const int MAXN = 501; const int MAXM = 101; long double F[MAXM][MAXN] = {0}; unsigned long cost[MAXM][MAXN] = {0}; unsigned long s[MAXM][MAXN] = {0}; bool mark[MAXM][MAXN] = {false}; //FILE * fin = fopen ("E:/Algorithm/Timus/data.txt", "r"); FILE * fin = stdin; int M = 0; int N = 0; fscanf (fin, "%d%d", &M, &N); int i = 0; int j = 0; for (i = 1; i <= M; i++) { for (j = 1; j <= N; j++) { fscanf (fin, "%d", &cost[i][j]); } } for (j = 1; j <= N; j++) { F[M][j] = cost[M][j]; } unsigned long result = 1e11; for (i = M - 1; i >= 1; i--) { int minIndex = 0; long double min = 1e20; for (j = 1; j <= N; j++) { if (F[i+1][j] + cost[i][j] < min) { min = F[i+1][j] + cost[i][j]; minIndex = j; } } F[i][minIndex] = min; s[i][minIndex] = (i + 1) * 10 + minIndex; for (int j = 1; j <= N; j++) { if (mark[i][minIndex] == false) { mark[i][minIndex] = true; if (minIndex - 1 >= 1 && mark[i][minIndex-1] == false) { if (F[i+1][minIndex-1] + cost[i][minIndex-1] > F[i][minIndex] + cost[i][minIndex-1]) { F[i][minIndex-1] = F[i][minIndex] + cost[i][minIndex-1]; s[i][minIndex-1] = i * 10 + minIndex; } else { F[i][minIndex-1] = F[i+1][minIndex-1] + cost[i][minIndex-1]; s[i][minIndex-1] = (i + 1) * 10 + minIndex - 1; } } if (minIndex + 1 <= N && mark[i][minIndex+1] == false) { if (F[i+1][minIndex+1] + cost[i][minIndex+1] > F[i][minIndex] + cost[i][minIndex+1]) { F[i][minIndex+1] = F[i][minIndex] + cost[i][minIndex+1]; s[i][minIndex+1] = i * 10 + minIndex; } else { F[i][minIndex+1] =F[i+1][minIndex+1] + cost[i][minIndex+1]; s[i][minIndex+1] = (i + 1) * 10 + minIndex + 1; } } long double tempMin = 1e20; int tempIndex = minIndex; if (minIndex - 1 >= 1 && mark[i][minIndex-1] == false && tempMin > F[i][minIndex-1]) { tempMin = F[i][minIndex-1]; tempIndex = minIndex - 1; }
if (minIndex + 1 <= N && mark[i][minIndex+1] == false && tempMin > F[i][minIndex+1]) { tempMin = F[i][minIndex+1]; tempIndex = minIndex + 1; } minIndex = tempIndex; } } } int index = 0; for (j = 1; j <= N; j++) { if (result > F[1][j]) { result = F[1][j]; index = j; } } int X = 1; int Y = index; while (X >= 1) { printf ("%d\n", Y); int t = s[X][Y]; X = t / 10; Y = t % 10; } } |
|
|