龟兔赛跑

[编程题]龟兔赛跑

热度指数：1286 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 90M，其他语言180M
算法知识视频讲解

定义如下图所示的比赛地图：

S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。

输入描述:

第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1<n<=10000, 0<m<=1000000)。

输出描述:

输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。

示例1

输入

输出

-1

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

// 单源最短路径：多了一个速度
public class Main {

    public static void main( String[] args ) {
        Scanner in = new Scanner(System.in);
        double v1 = in.nextDouble(), v2 = in.nextDouble();
        int n = in.nextInt(), m = in.nextInt();
        List<List<long[]>> g1 = new ArrayList<>(); // 邻接表1 兔子 仅陆地
        List<List<long[]>> g2 = new ArrayList<>(); // 邻接表2 乌龟 陆地+水路
        for (int i = 0; i <= n; i++) {
            g1.add(new ArrayList<>());
            g2.add(new ArrayList<>());
        }
        while (m-- > 0) {
            int a = in.nextInt(), b = in.nextInt();
            long d = in.nextLong(), c = in.nextInt();
            if (c == 0) { // 陆地
                g1.get(a).add(new long[] {b, d}); // 无向图
                g1.get(b).add(new long[] {a, d});
            }
            g2.get(a).add(new long[] {b, d});
            g2.get(b).add(new long[] {a, d});
        }

        long path1 = Dijkstra(g1, 1, n);
        long path2 = Dijkstra(g2, 1, n);
        double diff = path1 / v1 - path2 / v2;
        System.out.println(diff < 0 ? 1 : diff == 0 ? 0 : -1);
    }

    private static long Dijkstra(List<List<long[]>> g, int start, int end) {
        int n = g.size() - 1;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<long[]> queue = new PriorityQueue<>((a, b)->a[1] < b[1] ? -1 : 1);
        dist[start] = 0;
        queue.offer(new long[] {start, 0});
        while (!queue.isEmpty()) {
            long[] u = queue.poll();
            int a = (int)u[0];
            long dis = u[1];
            if (dis > dist[a]) continue;

            for (long[] v : g.get(a)) {
                int b = (int)v[0];
                long newDis = dis + v[1];
                if (newDis < dist[b]) {
                    dist[b] = newDis;
                    queue.offer(new long[] {b, newDis});
                }
            }
        }
        return dist[end];
    }
}

发表于 2025-06-30 22:47:30 回复(0)