UVA 116 Unidirectional TSP (白书dp)

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=18206  
1
 /*
  2 题目大意：
  3 从第一列的任意一格出发，到子最后一列的任意一格，的最短路。（一开是理解错了，以为是到第n行m列那个格子，知道样例没过，才发现）
  4 每一格只能这样走
         
  5 
  6 
  7 
  8 而且第一行向上可以走到最后一行，
  9 最后一行向下是第一行
 10 */
 11 dp[i][j]存储 第[i][j]到一列的最短路
 12 状态转移方程为：
 13 dp[i][j]=min(dp[i-1][j+1],dp[i][j+1],dp[i+1][j+1]);
 14 next[i][j]后继节点
 15 #include<stdio.h>
 16 #define maxn 200
 17 #define inf 0xfffffff
 18 #include<string.h>
 19 int min(int x,int y)
 20 {
 21     if(x<y)return x;
 22     else return y;
 23 
 24 }
 25 int n,m,next[maxn][maxn];
 26 int dp[maxn][maxn],map[maxn][maxn];
 27 void init()
 28 {
 29     int i,j;
 30     memset(next,0,sizeof(next));
 31     for(i=0;i<=n;i++)
 32     {
 33 
 34         for(j=0;j<=m;j++)
 35           dp[i][j]=inf;
 36     }
 37    for(i=1;i<=n;i++)
 38    {
 39        dp[i][m]=map[i][m];
 40    }
 41 }
 42 int  dfs(int x,int y)
 43 {
 44     int sum,d1,d3;
 45 
 46     if(y>m)return inf;
 47     if(dp[x][y]!=inf)return dp[x][y];
 48 
 49     int k;
 50     int x1,x2,x3;
 51 
 52     if(x-1==0)d1=n;
 53     else d1=x-1;
 54     if(x+1>n)d3=1;
 55     else d3=x+1;
 56 
 57     x1=dfs(d1,y+1);
 58     x2=dfs(x,y+1);
 59     x3=dfs(d3,y+1);
 60 
 61     if(x1>=inf&&x2>=inf&&x3>=inf){dp[x][y]=inf;return inf;}
 62     else
 63     {
 64         if(x1<x2)
 65         {
 66             sum=x1;
 67             k=d1;
 68         }
 69         else
 70         {
 71             if(x1==x2)
 72             {
 73                k=min(d1,x);
 74                sum=x1;
 75             }
 76             else
 77             {
 78                 k=x;
 79                 sum=x2;
 80             }
 81 
 82         }
 83         if(sum>x3)
 84         {
 85             k=d3;
 86             sum=x3;
 87 
 88         }
 89         else
 90         {
 91             if(sum==x3)
 92             {
 93                 k=min(k,d3);
 94             }
 95         }
 96         next[x][y]=k;
 97 
 98     dp[x][y]=dp[k][y+1]+map[x][y];
 99     return dp[x][y];
100 
101     }
102 
103 
104 
105 }
106 int GET()
107 {
108     int k,i,sum=inf;
109     for(i=1;i<=n;i++)
110     {
111         if(dp[i][1]<sum)
112         {
113             k=i;
114             sum=dp[i][1];
115         }
116     }
117     for(i=1;i<=m;i++)
118     {
119         if(i==1)
120         printf("%d",k);
121         else printf(" %d",k);
122         k=next[k][i];
123     }
124     printf("\n%d\n",sum);
125     return 0;
126 }
127 int main()
128 {
129     int i,j;
130     while(scanf("%d%d",&n,&m)!=EOF)
131     {
132 
133         for(i=1;i<=n;i++)
134         {
135             for(j=1;j<=m;j++)
136                scanf("%d",&map[i][j]);
137         }
138         init();
139        int ans=inf;
140        for(i=1;i<=n;i++)
141           dfs(i,1);
142 
143           /*for(i=1;i<=n;i++)
144           {
145               for(j=1;j<=m;j++)
146            {
147                 printf("%d ",dp[i][j]);
148 
149            }
150            printf("\n");
151           }*/
152 
153           GET();
154     }
155 
156 }