ACM: 116 - Unidirectional TSP

這一題要找一個table從左走到右的最小和路徑。題目寫的很像可以用brute force，但用brute force會超過time limit。後來想到DP的方法，很開心。DP真是一種很神奇的概念。

寫出來後一直runtime error，看很久才發現是表格頭接尾，尾接頭的部分沒有用餘數的方法讓他自動接，造成有漏洞會陣列越界讀取。改成餘數的方法就解決了。果然越好的演算法越不會有奇怪的洞啊。

CODE

#include <stdlib.h>
#include <stdio.h>

#define MAX_M 10
#define MAX_N 100

int main(){
  int i, j, k, min, tmp;
  int m, n, t[MAX_M][MAX_N], p[MAX_M][MAX_N];
  int mod[2] = {-1, 1};
  
  while( scanf("%d %d", &m, &n) == 2 ){
    for(i=0; i<m; i++)
      for(j=0; j<n; j++)
        scanf("%d", &t[i][j]);
    
    for(j=(n-2); j>=0; j--){
      for(i=0; i<m; i++){
        min = i;
        for(k=0; k<2; k++){
          tmp = (i+mod[k]+m) % m;
          if( t[tmp][j+1] < t[min][j+1] )
            min = tmp;
          else if( t[tmp][j+1] == t[min][j+1] )
            if( tmp < min )
              min = tmp;
        }/*k*/
        p[i][j] = min;
        t[i][j] += t[min][j+1];
      }/*i: row*/
    }/*j: col*/
    
    k = 0;
    for(i=1; i<m; i++)
      if( t[i][0] < t[k][0] )
        k = i;
    
    j = k;
    printf("%d", k+1);
    for(i=0; i<n-1; i++){
      printf(" %d", p[j][i]+1);
      j = p[j][i];
    }
    printf("\n%d\n", t[k][0]);
  }/*while input data*/ 
  
  exit(0);
}