算法 dijkstra

java 代码

import java.io.*;
import java.util.*;
public class Main{
    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int m, n;
    static int[][] grid = new int[101][101];
    static int[][] dis = new int[101][101];
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        String[] mn = reader.readLine().split(" ");
        m = Integer.parseInt(mn[0]);
        n = Integer.parseInt(mn[1]);
        for(int i = 0; i < 101; i++){
            Arrays.fill(grid[i], -1);
            Arrays.fill(dis[i], INF);
        }
        dis[1][1] = 0;
        for(int i = 0; i < n; i++){
            String[] line = reader.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            int c = Integer.parseInt(line[2]);
            grid[a][b] = c;
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[2]-b[2]); // x, y, cost, magic-0,1当前是魔法1, color
        pq.offer(new int[]{1, 1, 0, 0, grid[1][1]});
        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, 1, 0, -1};
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int cost = cur[2], magic = cur[3], preColor = cur[4];
            for(int i = 0; i < 4; i++){
                int x = cur[0] + dx[i], y = cur[1] + dy[i];
                if(x >= 1 && x <= m && y >= 1 && y <= m){
                    if(grid[x][y] >= 0){
                        int add = 0;
                        if(preColor != grid[x][y]){
                            add  = 1;
                        }
                        int nCost = cost + add;
                        if(nCost < dis[x][y]){
                            dis[x][y] = nCost;
                            pq.offer(new int[]{x, y, nCost, 0, grid[x][y]});
                        }

                    }else if(magic == 0){ // 有变魔术的权限
                        int nCost = cost + 2; // 变成和自己一样的颜色
                        if(nCost < dis[x][y]){
                            dis[x][y] = nCost;
                            pq.offer(new int[]{x, y, nCost, 1, preColor}); 
                        }
                    }
                }
            }
        }
        if(dis[m][m] == INF) System.out.println(-1);
        else System.out.println(dis[m][m]);
    }
}