单源最短路（优先队列优化的dijkstra算法）：PIPI的逃跑路线Ⅲ-蒲公英云

单源最短路（优先队列优化的dijkstra算法）：PIPI的逃跑路线Ⅲ

傷城~ 2023-10-06 20:07 91阅读 0赞

单源最短路（优先队列优化的dijkstra算法）：PIPI的逃跑路线Ⅲ

文章目录

单源最短路（优先队列优化的dijkstra算法）：PIPI的逃跑路线Ⅲ
- - 问题：
  - 思路：
  - 代码：

问题：

在这里插入图片描述

思路：

本题为单源最短路问题，麻烦点在于边权会不断变化，乍一看好似非常难，我们不可能每次去更新变化后的边权，仔细观察发现边权的变化函数f(x) = 1 / (1 - x)有点特殊，是有意设计成这样的，那么一定蕴含某个规律。设某条边的权值为x，经过一条道路后，权值变为1 / (1 - x)，那么再经过一条道路后呢？权值将变为f(f(x)) = 1 / (1 - 1 / (1 - x) ) = (x - 1) / x，不妨再试试，再经过一条道路后，权值变为f(f(f(x))) = 1 / (1 - (x - 1) / x) = x，权值又变回了x，即权值的变化处于一个循环中：
在这里插入图片描述
当我们发现这个边权变化函数的秘密，这个题目就很好求解了，其边权只有三种可能。
所以我们在bfs时设定一个步数step：当step%3=0，两点距离就是最原始的值w；当step%3=1，两点距离变为|1/(1-w)|，由于w都是大于1的，所以也就是1/(w-1);当step%3=2，两点距离变为|1-1/w|，1减去一个小数，其值肯定大于零，所以也就是1-1/w。于是我们开个dis[3][]的数组(dis[i][j]表示，step%3为i时，源点到达j点的最短距离 )，跑一遍最短路即可。

需注意的点：

我们每次将节点Node置入优先队列，Node除了包含节点编号，源点到该点的距离外，还需要包含源点到该点走的步数 % 3的值，步数信息应包含在结点中，而不是在bfs中修改
设step表示当前遍历的结点的步数信息，distance表示源点到该点的距离，weight表示该点到邻接点的距离，nextNode.index表示邻接点的编号，那么进行更新最短距离的判断为weight + distance < dis[(step + 1) % 3][nextNode.index]，注意dis数组的第一个索引为(step + 1) % 3，而不是step，因为从当前遍历点走到其邻接点，步数需加1

代码：

import java.util.*;
public class Main {
    static final double INF = 1000000000000000000.0 + 7;
    static Queue<Node> q = new PriorityQueue<>();
    static double[][] dis = new double[3][100002];
    static List<Node>[] adj = new ArrayList[100002];
    public static void main(String[] args) {
        int i, n, m, x, y, w;
        double ans;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (i = 0;i < 3;i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[0][1] = 0;
        for (i = 0;i < 100002;i++) {
            adj[i] = new ArrayList<Node>();
        }
        for (i = 0;i < m;i++) {
            x = scanner.nextInt();
            y = scanner.nextInt();
            w = scanner.nextInt();
            adj[x].add(new Node(y, w, 0));
            adj[y].add(new Node(x, w, 0));
        }
        q.add(new Node(1, 0, 0));
        dijsktra();
        ans = Math.min((Math.min(dis[0][n], dis[1][n])), dis[2][n]);
        if (ans < INF) {
            System.out.println(String.format("%.3f", ans));
        } else {
            System.out.println(-1);
        }
    }
    static void dijsktra() {
        Node node, nextNode;
        int step, index, i;
        double distance, weight;
        while (!q.isEmpty()) {
            node = q.poll();
            index = node.index;
            distance = node.distance;
            step = node.step;
            if (dis[step][index] < distance) {
                continue;
            }
            for (i = 0;i < adj[index].size();i++) {
                nextNode = adj[index].get(i);
                weight = step == 0 ? nextNode.distance : (step == 1 ? 1 / (nextNode.distance - 1.0) : (1 - 1.0 / nextNode.distance));
                if (weight + distance < dis[(step + 1) % 3][nextNode.index]) {
                    dis[(step + 1) % 3][nextNode.index] = weight + distance;
                    q.add(new Node(nextNode.index, dis[(step + 1) % 3][nextNode.index], (step + 1) % 3));
                }
            }
        }
    }
}
class Node implements Comparable<Node> {
    public int index;
    public double distance;
    public int step;
    public Node(int index, double distance, int step) {
        this.index = index;
        this.distance = distance;
        this.step = step;
    }
    @Override
    public int compareTo(Node o) {
        return (this.distance > o.distance) ? 1 : -1;
    }
}