Chains.Z edited 4 年，7 月前
根据 这辈子不可能刷oj的 大佬 的博客改进， 在此感谢大佬的代码
1. 去除了一些人类迷惑行为（指Node定义了time却不用）
2. 使用了更好的代码风格（指检查数组越界）
#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
const llt N = 1011;
const int big_int = 1e9;
const int dx[4] = {0, 0, 1, 1};
const int dy[4] = {-1, 1, 0, 1};
llt way[N][N];
llt time_used[N][N];
struct Node
{
int x, y;
Node(int i, int j) : x(i), y(j){};
};
void clear(llt board[][N])
{
for (llt i = 0; i < N; i++)
for (llt j = 0; j < N; j++)
board[i][j] = big_int;
}
int main()
{
llt n;
cin >> n;
clear(way);
clear(time_used);
for (llt i = 0; i < n; i++)
for (llt j = 0; j <= i; j++)
cin >> way[i][j];
queue<Node> order;
order.push(Node(0, 0));
time_used[0][0] = way[0][0];
while (!order.empty())
{
Node a = order.front();
order.pop();
for (int i = 0; i < 4; i++)
{
int xx = a.x + dx[i];
int yy = a.y + dy[i];
int time = time_used[a.x][a.y] + way[xx][yy];
if (yy >= 0 && yy <= xx && xx < n && (way[xx][yy] != big_int) && time < time_used[xx][yy])
{
time_used[xx][yy] = time;
order.push(Node(xx, yy));
}
}
}
cout << time_used[n - 1][0];
}