头像

xxdabc


访客:44

离线:10小时前



xxdabc
3天前

算法 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]);
    }
}



xxdabc
4天前

题目描述

    // 如果使用一维的dis[i], 优先队列保存{u, 槽下标},槽{-1, 0, 2}下标为0, 1, 2
    // 1层[0花销][槽下标1]->3层[5花销][槽下标2]->2层[9花销][槽下标0]->4层[15花销][槽下标2]
    // 1层[0花销][槽下标1]->3层[5花销][槽下标2]->5层[9花销][槽下标2]->4层[13花销][槽下标0](这时会更新dis[4])
    // dijkstra的过程中,dis[4]在到达队列元素{4, 2}和{4, 0}时产生了两个dis[4], 
    // dis[4]会被另一个更小的更新,但是队列中的槽下标却保持不变,导致此后计算cost的过程出错
    // 因此每个楼层dis还需要记录其产生的槽下标

样例

import java.io.*;
import java.util.*;
class Main{
    static int N;
    static int M;
    static int[] C;
    static int[][] dis;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        String[] l1 = reader.readLine().split(" ");
        N = Integer.parseInt(l1[0]);
        M = Integer.parseInt(l1[1]);
        C = new int[M];
        String[] l2 = reader.readLine().split(" ");
        int zero = -1;
        for(int i = 0; i < M; i++){
            C[i] = Integer.parseInt(l2[i]);
            if(C[i] == 0) zero = i;
        }
        dis = new int[N + 1][M];//dis[i][j] i为楼层, j为控制槽下标
        for(int i = 1; i <= N; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[1][zero] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->dis[a[0]][a[1]]-dis[b[0]][b[1]]);
        pq.offer(new int[]{1, zero});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int u = cur[0];
            int k = cur[1];
            for(int i = 0; i < M; i++){
                int v = u + C[i];
                if(v < 1) continue;
                if(v > N) break;
                int cost = Math.abs(u - v)*2;
                cost += Math.abs(i - k);
                if(dis[v][i] > dis[u][k] + cost){
                    dis[v][i] = dis[u][k] + cost;
                    pq.offer(new int[]{v, i});
                }
            }
        }
        int ans = INF;
        for(int i = 0; i < M; i++){
            ans = Math.min(ans, dis[N][i]);
        }
        if(ans == INF) ans = -1;
        System.out.println(ans);
    }
}



xxdabc
6天前
import java.io.*;
import java.util.*;
class Main{
    static int N = 1005;
    static int M = 10005;
    static int[] h = new int[N];
    static int[] adj = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[][] dis = new int[N][2];// dis[i][0] s到i点的最短路  dis[i][1] s到i点的次短路
    static int[][] cnt = new int[N][2];// cnt[i][0] s到i点的最短路条数 cnt[i][1] s到i点的次短路条数
    static int p;
    static void add(int a, int b, int c){
        adj[p] = b; ne[p] = h[a]; w[p] = c; h[a] = p++;
    }
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int n, m, s, t;
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        int T = Integer.parseInt(reader.readLine());
        for(int i = 0; i < T; i++){
            String[] l1 = reader.readLine().split(" ");
            n = Integer.parseInt(l1[0]);
            m = Integer.parseInt(l1[1]);
            p = 0;
            Arrays.fill(h, -1);
            for(int j = 0; j < m; j++){
                String[] line = reader.readLine().split(" ");
                int a = Integer.parseInt(line[0]);
                int b = Integer.parseInt(line[1]);
                int c = Integer.parseInt(line[2]);
                add(a, b, c);
            }
            String[] l2 = reader.readLine().split(" ");
            s = Integer.parseInt(l2[0]);
            t = Integer.parseInt(l2[1]);
            System.out.println(dijkstra());
        }
    }
    public static int dijkstra(){
        for(int j = 0; j < N; j++) {
            Arrays.fill(dis[j], INF);
            Arrays.fill(cnt[j], 0);
        }
        dis[s][0] = 0; dis[s][1] = 0; cnt[s][0] = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]);
        pq.offer(new int[]{s, 0});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int u = cur[0];
            int dist = cur[1];
            int k = -1; 
            //dist对应u的最短最短路时k=0, 次短路时k=1,否则说明之前dis[u]已找到更优路,dist为次次次次路
            if(dist == dis[u][0]) k = 0;
            else if(dist == dis[u][1]) k = 1;
            if(k == -1) continue; // dist轮到的时候,dis[u][]已经更新了,那么这个dist就没有意义了
            for(int i = h[u]; i != -1; i = ne[i]){
                int v = adj[i];
                int newDist =  dist + w[i];
                if(dis[v][0] > newDist){
                    // 0 表示最短路,1表示次短路
                    // 如果要更新最短路,那么意味着同时要更新次短路(原来的最短路变成了次短路)
                    dis[v][1] = dis[v][0];
                    cnt[v][1] = cnt[v][0];
                    dis[v][0] = newDist;
                    cnt[v][0] = cnt[u][k];
                    pq.offer(new int[]{v, newDist});
                }else if(dis[v][0] == newDist){
                    cnt[v][0] += cnt[u][k];
                }else if(dis[v][1] > newDist){
                    dis[v][1] = newDist;
                    cnt[v][1] = cnt[u][k];
                    pq.offer(new int[]{v, newDist});
                }else if(dis[v][1] == newDist){
                    cnt[v][1] += cnt[u][k];
                }
            }
        }
        if(dis[t][0] == dis[t][1] - 1) return cnt[t][0] + cnt[t][1];
        return cnt[t][0];
    }
}