DP——地道战

Description

大家一定看过地道战的电视吧。话说小兵张嘎有一回也跑去支援地道战了。那是河北的一个小镇里，这个小镇比较复杂，什么样的人都有。所以张嘎不能走大街，只能在地道里走。但根据地质情况不同，所以同样长的街道，地道里要走的时间可能不一样。当然每条街道下面都有地道，而且在街道连接处地道也有连接。有一天张嘎在A处，突然发现有大部队的敌军前来，所以他必须以尽快的速度跑到B处通知分队隐蔽，每条地道上都标出了他要走的时间。请帮他算一下，怎么走时间最短。

               A +---2---+---3---+----1---+----2---+
                 |       |       |        |        |
                 2       1       2        2        3
                 |       |       |        |        |
                 +---2---+---3---+----4---+---5----+
                 |       |       |        |        |
                 3       4       1        2        3
                 |       |       |        |        |
                 +---2---+---2---+---1----+---4----+
                 |       |       |        |        |
                 2       2       1        3        4
                 |       |       |        |        |
                 +---1---+---3---+---2----+---3----+ B

Input

有多个测试案例。每个测试案例，第1行输入2个整数N和M (1 <= n,m <=100)分别表示横向的街道的条数和纵向街道的条数。以下n行每行输入各段地道（横向）需要的时间，每行按从左到右的顺序一下m行每行输入各段地道（纵向）需要的时间，每列按从上到下的顺序处理到文件末尾

Output

对每个测试案例输出一行，输出他从A到B的最短时间

Sample Input

Sample Output

HINT

只能向下或向右

大意：求最短路就是另所有的路为无穷大，能走的取最小值，最后输出dp[n][m]，这道题的数据处理有点难..

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int main()
{
    int dp[110][110];
    int x[110][110],y[110][110];
    int n,m;
    while(~scanf("%d%d",&n,&m)){
    //heng
    for(int i = 0; i <= n ;i++)
        for(int j = 0 ; j <= m ;j++)
          x[i][j] = y[i][j] = dp[i][j] = inf;
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <= m-1 ;j++){
            scanf("%d",&x[i][j]);
        }
    }
    //shu
    for(int i = 1; i <= m ;i++){
        for(int j = 1; j <= n-1 ;j++){
            scanf("%d",&y[i][j]);
        }
    }
    dp[1][1] = 0;
    for(int i = 1;i <= n;i++){
      for(int j = 1; j <= m;j++){
            if(i == 1 && j == 1)
            continue;
           dp[i][j] = 0;
           dp[i][j] +=min(dp[i-1][j] + y[j][i-1],dp[i][j-1]+x[i][j-1]);
       }
     }
    printf("%d
",dp[n][m]);
    }
    return 0;
}

View Code