这种做法比较简单，代码量也比较少，但是局限性也很大，只能应付最短路符合拓扑序的情况
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N];
int f[N][N];
bool change[N][N]; // 标记是否是修改过颜色的点，还得记得及时清零，因为魔法会失效
void wk(const int &i, const int &j, int x, int y) { // 状态转移
if (change[i][j]) { // 清空魔法
change[i][j] = 0, a[i][j] = -1;
}
if (a[i][j] == -1) {
if (change[x][y]) return;
a[i][j] = a[x][y];
change[i][j] = 1;
f[i][j] = min(f[i][j], f[x][y] + 2);
}
else if (a[i][j] == a[x][y]) f[i][j] = min(f[i][j], f[x][y]);
else if (a[i][j] != a[x][y]) f[i][j] = min(f[i][j], f[x][y] + 1);
if (change[x][y]) { // 清空魔法
change[x][y] = 0, a[x][y] = -1;
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
memset(a, -1, sizeof(a));
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= m; ++i) {
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
a[x][y] = c;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == 1 && j == 1) {
f[i][j] = 0;
continue;
}
wk(i, j, i - 1, j);
wk(i, j, i, j - 1);
}
}
printf("%d\n", f[n][n]);
}