Anaconda C语言 java设计模式 Angular log4j performance file validation parsing checkbox static 后台页面模板 河南普通话 java设计模式视频 pmp教程 广告投放系统源码 tomcat调优和jvm调优 pyhton中异常和模块 python中的for循环 python处理json文件 java集成 java中instanceof java文件读写 linux教程 linuxtar命令 html实例教程 flash实例 音频频谱分析软件 摩斯密码翻译 枪神传说辅助 动态加载js js转int 刷机工具下载 flash基础 识别音乐的软件 js倒计时 R语言初学者指南 mac强制重启 证书小精灵 sdm439
当前位置: 首页 > 学习教程  > 编程语言

AcWing 853. 有边数限制的最短路(Bellman-Ford算法)

2020/8/11 19:15:44 文章标签:

时间复杂度:O(nm)

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

请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。

注意:图中可能 存在负权回路 。

输入格式

第一行包含三个整数n,m,k。

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

输出格式

输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围

1≤n,k≤5001≤n,k≤500,
1≤m≤100001≤m≤10000,
任意边长的绝对值不超过10000。

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

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

class Main{
    static int n = 0, m = 0, k = 0;
    static int N = 10010;
    static int[][] edges = new int[N][3];
    static int[] dist = new int[510];
    static int[] backup = new int[510];
    static int bellmanFord(){
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for(int i = 0; i < k; ++i){
            backup = Arrays.copyOf(dist, N);
            for(int j = 1; j <= m; ++j){
                int a = edges[j][0], b = edges[j][1], w = edges[j][2];
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if(dist[n] >= 0x3f3f3f3f / 2)return -1;
        return dist[n];
        
    }
    
    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]);
        k = Integer.valueOf(params[2]);
        for(int i = 1; i <= m; ++i){
            String[] info = buf.readLine().split(" ");
            edges[i][0] = Integer.valueOf(info[0]);//入
            edges[i][1] = Integer.valueOf(info[1]);//出
            edges[i][2] = Integer.valueOf(info[2]);//权值
        }
        int cond = bellmanFord();
        if(cond != -1){
            System.out.print(cond);
        }else{
            System.out.print("impossible");
        }
        
    }
}

 


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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?