顺序查找 performance rest events download scripting vue标签 vue修改样式 python简易教程 python分析 python程序代码 java如何使用 java安装教程 unix操作系统下载 黑帮之地修改器 win10长期服务版 亚索刀光特效包 苹果手机老是自动重启 winhex使用教程 考试练习系统 hexworkshop 微信彩色字 excel应用大全 证书小精灵 js给标签添加属性 万能低格工具还原u盘 videoview 华为杂志锁屏怎么设置 python编辑器 g4560配什么显卡 分割字符串 极速pdf转word 易语言皮肤模块 h5支付接口 点状字体 祸星龙 js弹出框 网卡flash导入音乐 文件解密软件 打印机暂停
当前位置: 首页 > 学习教程  > 编程语言

AcWing 851. spfa求最短路(SPFA算法)

2020/8/11 20:44:13 文章标签:

给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式

输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出”impossible”。

数据范围

1≤n,m≤1051≤n,m≤105,
图中涉及边长绝对值均不超过10000。

输入样例:

3 3
1 2 5
2 3 -3
1 3 4

输出样例:

2

SPFA思想:

优化BellmanFord算法:当距离更新的时候(也就是它的距离变小了,它变小了,自然后面变小的几率更大),把它插进队列去更新。



import java.io.*;
import java.lang.*;
import java.util.*;

class Main{
    
    static int n = 0, m = 0, N = 100010;
    static int[] h = new int[N], w = new int[N], e = new int[N], ne = new int[N];
    static int idx = 1;
    static Deque<Integer> q = new ArrayDeque<>();
    static int[] dist = new int[N];
    static boolean[] f = new boolean[N];
    static int spfa(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        f[1] = true;
        q.offer(1);
        while(q.size() != 0){
            int a = q.poll();
            f[a] = false;
            for(int i = h[a]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[a] + w[i]){//遇到小的就更新
                    dist[j] = dist[a] + w[i];//更新距离
                    if(!f[j]){//如果之前没插入则插入,差如果就不插入了
                        q.offer(j);
                        f[j] = true;
                    }
                }
            }
        }
        if(dist[n] == 0x3f3f3f3f)return -1;
        return dist[n];
    }
    
    static void add(int a, int b, int wc){
        e[idx] = b; w[idx] = wc; ne[idx] = h[a]; h[a] = idx++;
    }
    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String[] params = buf.readLine().split(" ");
        n = Integer.valueOf(params[0]);
        m = Integer.valueOf(params[1]);
        Arrays.fill(h, -1);
        for(int i = 1; i <= m; ++i){
            String[] info = buf.readLine().split(" ");
            int a = Integer.valueOf(info[0]);
            int b = Integer.valueOf(info[1]);
            int wc = Integer.valueOf(info[2]);
            add(a, b, wc);
        }
        int res = spfa();
        if(res == -1){
            System.out.print("impossible");
        }else
            System.out.print(res);
    }
}

 


本文链接: http://www.dtmao.cc/news_show_100404.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?