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
     
       16 #define maxn 200 17 #define inf 0xfffffff 18 #include
      
        19 int min(int x,int y) 20 { 21     if(x
       
        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
        
         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]