请在下方输入要搜索的题目：

问题描述给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。输入格式第一行两个整数n, m。接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。输出格式共n-1行,第i行表示1号点到i 1号点的最短路。样例输入 3 3 1 2 -1 2 3 -1 3 1 2 样例输出 -1 -2 数据规模与约定对于10%的数据,n = 2,m = 2。对于30%的数据,n

问题描述给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。输入格式第一行两个整数n, m。接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。输出格式共n-1行,第i行表示1号点到i 1号点的最短路。样例输入 3 3 1 2 -1 2 3 -1 3 1 2 样例输出 -1 -2 数据规模与约定对于10%的数据,n = 2,m = 2。对于30%的数据,n

发布时间：2024-10-30 16:33:13

推荐参考答案 ( 由快搜搜题库官方老师解答 )

联系客服

答案：锦囊1 使用最短路算法。锦囊2 使用Dijkstra算法,此图的边数比点数的平方要少很多,因此应该使用带堆优化的Dijkstra。 import java.io.*; import java.util.*; class Main { static int n,m; static int[] u; static int[] v; static int[] w; static int[] d; static int[] first; static int[] next; static Queue q=new LinkedList(); static boolean[] inq; public static void main(String[] args) throws IOException { int i; BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in)); String str = bfr.readLine(); String[] s = str.split("\\s"); n=Integer.parseInt(s[0]); m=Integer.parseInt(s[1]); n ; m ; u=new int[m]; v=new int[m]; w=new int[m]; first=new int[n]; next=new int[m]; d=new int[n]; inq=new boolean[n]; for(i=1;i

专业技术学习

相关试题

专业技术学习

搜搜题库系统

卫生法学题库公考面试题库医考题库模拟考试题库试卷题库社区题库工会考试题库社区工作者考试题库申论题库宪法知识题库国家电网企业文化题库教师进城考试题库医学职业能力测试题库行政执法考试题库社工题库考研政治题库普通话考试题库幼儿园案例分析题库乡镇公务员面试题库注册税务师题库