题目地址：Ural 1119
因为还有一个可不可以穿的问题，所以需要再加一维。0代表可穿不可穿，可穿设置成0，不可穿就设置成无穷大。1代表当前这格的最短距离。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include 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; }