本文主要是介绍Ural 1119 Metro（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：Ural 1119
因为还有一个可不可以穿的问题，所以需要再加一维。0代表可穿不可穿，可穿设置成0，不可穿就设置成无穷大。1代表当前这格的最短距离。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
double x=sqrt(20000.0);
double dp[3][1001][1001];
double min1(double x, double y)
{if(x>y)return y;return x;
}
int main()
{int n, m, i, j, k, a, b, ans;while(scanf("%d%d",&n,&m)!=EOF){scanf("%d",&k);for(i=0; i<=n+1; i++)for(j=0; j<=m+1; j++){dp[0][i][j]=INF;dp[1][i][j]=INF;}while(k--){scanf("%d%d",&a,&b);dp[0][a][b]=0;}dp[1][1][1]=0;for(i=1; i<=n+1; i++){for(j=1; j<=m+1; j++){if(i==j&&i==1){continue ;}dp[1][i][j]=min1(min1(dp[1][i-1][j],dp[1][i][j-1])+100,dp[0][i-1][j-1]+dp[1][i-1][j-1]+x);}}/*for(i=1;i<=n+1;i++){for(j=1;j<=m+1;j++){printf("%.2lf ",dp[1][i][j]);}puts("");}*/printf("%d\n",(int)(dp[1][n+1][m+1]+0.5));}return 0;
}
这篇关于Ural 1119 Metro（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
