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

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

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

#### 文章目录 ####

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

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

本题为单源最短路问题，麻烦点在于边权会不断变化，乍一看好似非常难，我们不可能每次去更新变化后的边权，仔细观察发现边权的变化函数`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，即权值的变化处于一个循环中：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
  当我们发现这个边权变化函数的秘密，这个题目就很好求解了，其边权只有三种可能。  
  所以我们在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;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ee4e6a0fc8cf4c94ac1922717e769749.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/e5b193ed47d143ba8e89a0629cc00c3d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/c970d6e2314f4fcfb229c9b4f4a34eed.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16