AcWing 1018. 最低通行费
原题链接
简单
作者:
面向yxc编程
,
2021-02-19 22:34:59
,
所有人可见
,
阅读 280
合理利用哨兵使代码精简
#include<bits/stdc++.h>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
//求max时可以用达不到的最小值做哨兵,求min时可以用达不到的最大值做哨兵
int f[N][N],w[N][N];
int main(){
memset(f,0x3f,sizeof f);
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1){
f[1][1]=w[1][1];//初始化
continue;//人为的设置一个哨兵即可
}
f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];
}
}
cout<<f[n][n]<<endl;
}