AcWing 1018. 最低通行费
原题链接
简单
作者:
stedv
,
2019-09-23 15:18:11
,
所有人可见
,
阅读 733
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int a[N][N],s[N][N],t,n,m;
int main()
{
memset(a,0,sizeof(a));
memset(s,0,sizeof(s));
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==1)s[i][j]=s[i][j-1]+a[i][j];
else if(j==1)s[i][j]=s[i-1][j]+a[i][j];
else s[i][j]=min(s[i-1][j],s[i][j-1])+a[i][j];
}
printf("%d",s[n][n]);
return 0;
}