uq_37591206429

用户名：uq_37591206429

访问量：234

签　名：

等　　级
排　　名	6634
经　　验	1396
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Dijkstra和spfa
浏览：25

数据范围可以用Floyd
浏览：23

你可能喜欢

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

Dijkstra和spfa

　　作者: uq_37591206429　　　　发表时间：2024-02-09 12:59:54 浏览：25　|　评论：0　

原题链接：热浪(heatwv)

朴素版Dijkstra

```java
import java.io.*;
import java.util.*;

public class Main {
    static int N = 2505, T, C, Ts, Te;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        C = sc.nextInt();
        Ts = sc.nextInt();
        Te = sc.nextInt();
        for (int i = 0; i < N; i++)
            Arrays.fill(g[i], 0x3f3f3f3f);
        while (C-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            g[a][b] = c;
            g[b][a] = c;
        }
        dijkstra();
        System.out.println(dist[Te]);
    }
    public static void dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[Ts] = 0;
        for (int i = 0; i < T; i++) {
            int t = -1;
            for (int j = 1; j <= T; j++)
                if (!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;
            st[t] = true;
            for (int j = 1; j <= T; j++)
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        }
    }
}
```

堆优化版Dijkstra

```java
import java.io.*;
import java.util.*;

public class Main {
    static int N = 2505, M = 6200 * 2 + 10, T, C, Ts, Te, idx;
    static int[] dist = new int[N], e = new int[M], ne = new int[M], w = new int[M], h = new int[N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        C = sc.nextInt();
        Ts = sc.nextInt();
        Te = sc.nextInt();
        Arrays.fill(h, -1);
        while (C-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            insert(a, b, c);
            insert(b, a, c);
        }
        dijkstra();
        System.out.println(dist[Te]);
    }
    public static void insert(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static void dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[Ts] = 0;
        PriorityQueue<Point> q = new PriorityQueue<>((a, b) -> (a.dis - b.dis));
        q.add(new Point(Ts, 0));
        for (int i = 0; i < T; i++) {
            Point p = q.remove();
            int x = p.x, dis = p.dis;
            if (st[x]) continue;
            st[x] = true;
            for (int j = h[x]; j != -1 ; j = ne[j]) {
                int t = e[j];
                if (dis + w[j] < dist[t]) {
                    dist[t] = dis + w[j];
                    q.add(new Point(t, dist[t]));
                }
            }
        }
    }
}
class Point {
    int x, dis;
    public Point(int x, int dis) {
        this.x = x;
        this.dis = dis;
    }
}
```

spfa

```java
import java.io.*;
import java.util.*;

public class Main {
    static int N = 2505, M = 6200 * 2 + 10, T, C, Ts, Te, idx;
    static int[] dist = new int[N], e = new int[M], ne = new int[M], w = new int[M], h = new int[N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        C = sc.nextInt();
        Ts = sc.nextInt();
        Te = sc.nextInt();
        Arrays.fill(h, -1);
        while (C-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            insert(a, b, c);
            insert(b, a, c);
        }
        spfa();
        System.out.println(dist[Te]);
    }
    public static void insert(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static void spfa() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[Ts] = 0;
        LinkedList<Integer> q = new LinkedList<>();
        q.add(Ts);
        while (!q.isEmpty()) {
            int p = q.remove();
            st[p] = false;
            for (int j = h[p]; j != -1 ; j = ne[j]) {
                int t = e[j];
                if (dist[p] + w[j] < dist[t]) {
                    dist[t] = dist[p] + w[j];
                    if (!st[t])
                        q.add(t);
                }
            }
        }
    }
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

uq_37591206429

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

十->二进制转换（C语言代码）

Dijkstra和spfa

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

校门外的树（C语言代码）

母牛的故事（C语言代码）

Tom数（C语言代码）

1054题解

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

1162答案错误，为什么

小O的图案（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

uq_37591206429

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

汽水瓶 （C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

十->二进制转换 （C语言代码）

Dijkstra和spfa

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

校门外的树 （C语言代码）

母牛的故事 （C语言代码）

Tom数 （C语言代码）

1054题解

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

1162答案错误，为什么

小O的图案 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

十->二进制转换（C语言代码）

　　评论区

校门外的树（C语言代码）

母牛的故事（C语言代码）

Tom数（C语言代码）

小O的图案（C语言代码）