美团2024春招第9场算法第二题

测试用例

3 3

1 2 3

3 4 5

4 3 6

目标答案：19

最短路问题

考虑使用dijkstra

import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class mt2 {
    static int n,m;
    static StreamTokenizer stk = new StreamTokenizer(new java.io.BufferedReader(new java.io.InputStreamReader(System.in)));

    static int[][] graph = new int[1050][1050];
    static boolean[][] vis = new boolean[1050][1050];
    //构建一个点图
    static int getInt(){
        try{
            stk.nextToken();
            return (int)stk.nval;
        }catch(Exception e){
            return -1;
        }
    }

    public static void main(String[] args) {
        n = getInt();
        m = getInt();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                graph[i][j] = getInt();
            }
        }
        node end = new node((1+n)/2, (1+m)/2, graph[(1+n)/2][(1+m)/2]);//在中点相见
        long sum = 0;
        node start = new node(1,1,graph[1][1]);
        sum += dijkstra(start,end);
        start = new node(n,m,graph[n][m]);
        sum += dijkstra(start,end);
        System.out.println(sum - graph[(1+n)/2][(1+m)/2]);//因为中心点会被同时算两次，去重
    }
    static class node{
        int x;
        int y;
        int value;
        public node(int x, int y, int value){
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }
    static long dijkstra(node start,node end){{
        long sum = start.value;
            PriorityQueue<node> pq = new PriorityQueue<>((a,b)->b.value-a.value);
            pq.add(start);
            while(!pq.isEmpty()){
                node now = pq.poll();
                if(now.x == end.x && now.y == end.y) break;//检查是否到达终点
                if(vis[now.x][now.y])continue;
                vis[now.x][now.y] = true;//标记访问
                int[][] path = {{0,1},{0,-1},{1,0},{-1,0}};//上下左右
                int x = now.x;
                int y = now.y;
                long max = Integer.MIN_VALUE;
                long max_value = 0;
                for(int i = 0; i < 4;i++){
                    int idx = x + path[i][0];
                    int idy = y + path[i][1];
                    if(max < graph[idx][idy] + sum){//如果当前点+总和大于最大值，则更新最大值
                        max = graph[idx][idy] + sum;
                        if(!vis[idx][idy]){
                            max_value = graph[idx][idy];//保存当前点的值，必须是未访问过的
                        pq.add(new node(idx,idy,graph[idx][idy]));//添加进队列中
                        }
                    }
                }

                sum += max_value;
            }
            return sum;
    }
    }
}

关于dijkstra堆优

static void Dijkstra(int s){//堆优化版本
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[s] = 0;
        //压入格式为{v,w}
        PriorityQueue<node> que = new PriorityQueue<>((a,b) -> a.weight - b.weight);//从小到大使用优先队列

        que.offer(new node(s,0));

        while(!que.isEmpty()){
            node now_point = que.poll();
            int u = now_point.ponit;
            int w = now_point.weight;
            if(vis[u]) continue;//将该点置为已访问
            vis[u] = true;
            //遍历该点的所有邻接点
            for(int i = head[u]; i != -1; i = edges[i].next){;
                int v = edges[i].to;//到达点
                //如果dist[到达点] > 当前点的最短距离+到达下一个点的距离 置换
                if(dist[v] > w + edges[i].weight){
                    dist[v] = w + edges[i].weight;
                    if(!vis[v]){
                        que.offer(new node(v,dist[v]));
                    }
                }
            }
        }
    }

已经写的很详细了，不在赘述