地道战

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 959 Solved: 615

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

 1 #include<stdio.h>
 2 int min(int a,int b)
 3 {
 4     return a<=b?a:b;
 5 }
 6 
 7 int main()
 8 {
 9   //  freopen("a.txt","r",stdin);
10     int m,n;
11     int cross[200][200],vertical[200][200];
12     int i,j,k;
13     int dp[250][250];
14     while(scanf("%d%d",&m,&n)==2)
15     {
16         for(i=0;i<=m;i++)
17             for(j=0;j<=n;j++)
18             {
19                 cross[i][j]=99999999;
20                 vertical[i][j]=99999999;
21             }
22         for(i=1;i<=m;i++)
23         {
24            // printf("
");
25             for(j=1;j<=n-1;j++)
26             {
27                 scanf("%d",&cross[i][j]);
28          //       printf("%-4d",cross[i][j]);
29             }
30         }
31        // printf("
");
32         for(i=1;i<=n;i++)
33         {
34           //  printf("
");
35             for(j=1;j<=m-1;j++)
36             {
37                 scanf("%d",&vertical[i][j]);
38               //  printf("%-4d",vertical[i][j]);
39             }
40         }
41      //   printf("
");
42         for(i=0;i<=m;i++)
43             for(j=0;j<=n;j++)
44             {
45                 dp[i][j]=99999999;
46             }
47 
48         dp[1][1]=0;
49         for(i=1;i<=m;i++)
50             for(j=1;j<=n;j++)
51             {
52                 if(i==1&&j==1)
53                     continue;
54                 dp[i][j]=0;
55                 dp[i][j]+=min(dp[i-1][j]+vertical[j][i-1],dp[i][j-1]+cross[i][j-1]);
56             }
57       /*  for(i=1;i<=m;i++)
58         {
59             printf("
");
60             for(j=1;j<=n;j++)
61             {
62                 printf("%-4d",dp[i][j]);
63             }
64         }  */
65         printf("%d
",dp[m][n]);
66     }
67     return 0;
68 }

View Code

蛮简单的dp