1.染色时间 - 蓝桥云课
问题描述
小蓝有一个 n 行 m 列的白色棋盘，棋盘的每一个方格都可以被染成彩色。
每个方格有一个染色时间 tij，不同方格的染色时间可能不同。如果一个方格被触发了染色，这个方格就会在 tij 秒之后变成彩色，然后将自己上下左右四个方向相邻的方格触发染色。每个方格只能被触发染色一次，第一次触发之后的触发为无效触发。
给定每个方格的染色时间，在时刻 0 触发第一行第一列的方格染色，请问多长时间后整个棋盘完成染色。
输入格式
输入的第一行包含两个整数 n，m，分别表示棋盘的行数和列数。
接下来 n 行，每行 m 个正整数，相邻的整数之间用一个空格分隔，表示每个方格的染色时间。该部分的第 i 行第 j 个整数表示 tij，即第 i 行第 j 列的方格的染色时间。
输出格式
输出一行包含一个整数，表示整个棋盘完成染色的时间。
样例输入
3
1 2 3
4 5 6样例输出
12评测用例规模与约定
- 对于 30 的评测用例，1≤n,m≤10。
- 对于 60 的评测用例，1≤n,m≤50。
- 对于所有评测用例，1≤n,m≤500，1≤tij≤1000。
运行限制
- 最大运行时间：1s
- 最大运行内存：256M
思路：
问题本质与图论建模
-
触发机制类比边权：
-
每个方格的染色时间
t_ij可视为从该方格到其相邻方格的“边权”。 -
当一个方格完成染色（触发时间 +
t_ij），它才能触发相邻方格。相邻方格的触发时间等于当前方格的完成时间。
-
-
最长时间的计算：
-
所有方格完成染色的时间是其触发时间与自身染色时间之和。
-
最终答案即为所有方格中完成时间的最大值。
-
-
Dijkstra算法的适用性：
-
每个方格的触发时间需要尽可能早，这与Dijkstra求最短路径的思想一致。
-
优先队列确保每次处理当前触发时间最小的方格，保证后续更新的正确性。
-
Dijkstra算法的应用步骤
-
初始化触发时间：
-
起点
(0,0)的触发时间为0，其他方格初始化为无穷大（表示未被触发）。
-
-
优先队列处理：
-
每次取出队列中触发时间最小的方格，计算其完成时间。
-
更新相邻方格的触发时间：若通过当前路径更早触发，则更新并入队。
-
-
结果计算：
-
遍历所有方格，计算触发时间与染色时间之和的最大值。
-
为什么不是普通的bfs？假设路径A触发时间为5秒，路径B触发时间为3秒，但路径B的节点在队列中排在路径A之后。
BFS会先处理路径A的节点，错误地将相邻方格的触发时间设为5+t，而非更优的3+t。使用优先队列是为了保证触发时间的最优性。每个节点的触发时间可能通过多条路径到达，必须选择最小的值。优先队列通过贪心策略和动态更新，确保所有节点的触发时间被正确计算，从而准确得到整个棋盘完成染色的时间。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct Node{int time,x,y;
};
struct CompareNode
{bool operator()(const Node& a, const Node& b) {return a.time > b.time; }
};
int t[505][505], dis[505][505];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> t[i][j];}}memset(dis, 0x3f, sizeof dis);dis[1][1] = 0;priority_queue<Node, vector<Node>,CompareNode> pq;pq.push({0, 1, 1}); while (!pq.empty()) {auto node = pq.top();pq.pop();int time = node.time;int x = node.x;int y = node.y;if (time > dis[x][y]) {continue;}// int current_end = time + t[x][y];for (int k = 0; k < 4; ++k) {int tx = x + dx[k];int ty = y + dy[k];if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) {if (dis[tx][ty] > time + t[x][y]) {dis[tx][ty] = time + t[x][y];pq.push({time + t[x][y], tx, ty});}}}}int ans = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {ans = max(ans, dis[i][j] + t[i][j]);}}cout << ans << endl;return 0;
}
