分析一下import java.io.;import java.util.;public class ShortestPath { static class Edge { int to, weight; public Edge(int to, int weight) { this.to = to; this.weight = weight; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new FileReader("input.txt")); PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt"))); String[] line1 = br.readLine().split(" "); int n = Integer.parseInt(line1[0]); int m = Integer.parseInt(line1[1]); int start = 1; // 源顶点为1 List<List<Edge>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { String[] line = br.readLine().split(" "); int u = Integer.parseInt(line[0]); int v = Integer.parseInt(line[1]); int w = Integer.parseInt(line[2]); graph.get(u).add(new Edge(v, w)); } int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] = 0; PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i])); pq.offer(start); while (!pq.isEmpty()) { int u = pq.poll(); for (Edge e : graph.get(u)) { int v = e.to; int w = e.weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(v); } } } for (int i = 1; i <= n; i++) { pw.println(dist[i]); } br.close(); pw.close(); }}的时间复杂度
时间: 2024-04-20 10:27:27 浏览: 23
这段代码的主要算法是 Dijkstra 最短路径算法,时间复杂度为 O(mlogn),其中 n 表示图中的顶点数,m 表示图中的边数。具体分析如下:
1. 读入输入:时间复杂度为 O(1)。
2. 建立邻接表:对于每条边都要添加到邻接表中,因此时间复杂度为 O(m)。
3. 初始化距离数组和优先队列:数组初始化时间复杂度为 O(n),优先队列初始化时间复杂度为 O(nlogn)。
4. 进行 Dijkstra 算法:最坏情况下,每个顶点都会被遍历一遍,每次遍历需要从优先队列中弹出元素并进行操作,因此时间复杂度为 O(mlogn)。
5. 输出结果:时间复杂度为 O(n)。
综上所述,该程序的时间复杂度为 O(mlogn)。
相关问题
import java.util.Scanner; public class Test1 { 晋涛 public static void main(String[] args) { Sy
import java.util.Scanner;
public class Test1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入您的姓名:");
String name = scanner.nextLine();
.out.println("您好," + name + "!");
}
}
这段代码是一个简单的Java程序,它使用了Java标准库中的Scanner类来实现用户输入和输出。首先,我们通过创建Scanner对象来获取用户的输入。然后,使用nextLine()方法读取用户输入的姓名,并将其存储在name变量中。最后,通过System.out.println()方法将问候语和用户的姓名输出到控制台。
import java.util.InputMismatchException;
import java.util.InputMismatchException 是 Java 中的一个 import 语句,用于导入 java.util 包中的 InputMismatchException 类。InputMismatchException 是一个继承自 java.util.NoSuchElementException 的异常类,通常在输入不匹配的情况下抛出。例如,在使用 Scanner 类从控制台读取输入时,如果输入的数据类型与所需的数据类型不匹配,则会抛出 InputMismatchException 异常。
导入 java.util.InputMismatchException 类后,就可以在代码中使用该类,例如:
```
import java.util.Scanner;
import java.util.InputMismatchException;
public class MyClass {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
try {
int num = scanner.nextInt();
System.out.println("输入的数字是:" + num);
} catch (InputMismatchException e) {
System.out.println("输入的不是数字!");
}
}
}
```
在上面代码中,我们使用 Scanner 类从控制台读取输入,如果输入的不是数字,则会抛出 InputMismatchException 异常,并被 catch 块捕获并处理。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)