题目描述
一个商人穿过一个 N×N
的正方形的网格,去参加一个非常重要的商务活动。
他要从网格的左上角进,右下角出。
每穿越中间 1
个小方格,都要花费 1
个单位时间。
商人必须在 (2N−1)
个单位时间穿越出去。
而在经过中间的每个小方格时,都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用?
注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。
输入格式
第一行是一个整数,表示正方形的宽度 N
。
后面 N
行,每行 N
个不大于 100
的正整数,为网格上每个小方格的费用。
输出格式
输出一个整数,表示至少需要的费用。
数据范围
1≤N≤100
样例
输入样例:
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
输出样例:
109
样例解释
样例中,最小值为 109=1+2+5+7+9+12+19+21+33
用一下算法基础课的dijkstra算法来解决这道题
算法1
() $O(n^2)$
我们可以用dijkstra算法来解决这个问题
用两个数组来解决:a[n][n]存图;f[n][n]存结果
f[x][y]存从起点a[1][1]到a[x][y]的最短距离
关键步骤:
判断:f[x][y] > f[t.first][t.second] + a[x][y];
更新:f[x][y] = f[t.first][t.second] + a[x][y];
上代码:
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED]PII;
const int M=110;
int n;
int w;
int a[M][M];
int f[M][M];
int dx[2]={0,1};
int dy[2]={1,0};
int main(){
memset(a,0x3f,sizeof a);
memset(f,0x3f,sizeof f);
queue[HTML_REMOVED]p;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
f[1][1]=a[1][1];
p.push(make_pair(1,1));
while(!p.empty()){
auto t=p.front();
p.pop();
for(int i=0;i<2;i++){
int x=dx[i]+t.first;
int y=dy[i]+t.second;
if(x>0&&y>0&&x<=n&&y<=n&& f[x][y] > f[t.first][t.second] + a[x][y]){
f[x][y] =f[t.first][t.second] + a[x][y];
p.push(make_pair(x,y));
}
}
}
cout<<f[n][n]<<endl;
return 0;
}
时间复杂度O(N*N);
参考文献:
y总算法基础课
y总yyds!!!!