龟兔赛跑

通用Dijkstra求全路径点到点的距离代码，稍微修改就可以适用本题

/*
Dijkstra算法求单源无向图最短路径
*/
#include <bits/stdc++.h>
using namespace std;
struct node {
    int point, value;
    node(int a, int b) // 构造
    {
        point = a;
        value = b;
    }
    // 重载<操作符 由小到大排序
    bool operator<(const node &a) const
    {
        // 对小于运算符进行重载，如果两个值相等，那么继续判断point，如果不等，则返回false
        if (value == a.value) {
            return a.point < point;
        } else {
            return a.value < value;
        }
    }
};
class Dijkstra{
public:
    Dijkstra(int count):n(count){
        processE();//处理输入
        result = vector<vector<int>>(count,vector<int>(count));
    };
    //求解无向图中所有点之前的距离
    void solver(bool debug=true){
        for(unsigned int i=1;i<=n;++i){
            result.push_back(dijkstra(i));
            if(debug){
                for(int x:result.back()){
                    cout<<x<<' ';
                }
                cout<<endl;
            }
        }
    }
    //start是实际的标号，从1开始，在处理中数组从0开始
    vector<int> dijkstra(int start)
    {    vector<int> dis(n+1,INT_MAX);
        priority_queue<node> q;//每次求解需要的优先队列
        dis[start] = 0;
        q.push(node(start, dis[start] ));

        while (!q.empty()) {
            node x = q.top();
            q.pop();
            for (int i = 0; i < e[x.point].size(); i++) {
                node y = e[x.point][i];
                // 核心思想：更新估算距离，松弛
                if (dis[y.point] > dis[x.point] + y.value) {
                    dis[y.point] = dis[x.point] + y.value;
                    q.push(node(y.point, dis[y.point]));
                }
            }
        }
        return vector<int>(dis.begin()+1,dis.end());
    }
    void processE(){
        //这个函数用来处理e[Ni]需要将start,end ,length添加到e[start]->(end,length)和e[end]->(start,length)
        //形如e[start].push_back(node(end[[2,1,1],[2,3,1],[3,4,1]], length));
        int a, b, c, k;
        char s;
        getchar();
        while(getchar() == '[') {
            scanf("%d%c%d%c%d%c%c", &a, &s, &b, &s, &c, &s, &s);
            e[a].push_back(node(b, c));
            e[b].push_back(node(a,c));
        }
    }
private:
    vector<vector<int>> result;//最后的结果矩阵
    const static int Ni = 101 ;//最大的边的集合
    vector<node> e[Ni];//用起点表示的边的集合
    int n ;//实际的边的个数


};




int main(){
    Dijkstra(4).solver();
}

同时到达，都足够聪明了，路上兔子背着乌龟，水里乌龟拖着兔子

import java.util.*;

public class Main {

    static class Graph {
        private Node start;
        private Node end;
        private final Map<Long, Node> map = new HashMap<>();
    }

    static class Node {
        final long id;
        final Map<Way, Node> wayMap = new TreeMap<>();
        Node(long id) {
            this.id = id;
        }
    }

    static class Way implements Comparable<Way> {
        long len;
        int type;

        Way(long len, int type) {
            this.len = len;
            this.type = type;
        }

        @Override
        public int compareTo(Way o) {
            return Long.compare(len, o.len);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long v1 = sc.nextLong();
        long v2 = sc.nextLong();
        long n = sc.nextInt();
        long m = sc.nextInt();

        Graph g = new Graph();
        for (int i = 0; i < m; i++){
            long src = sc.nextInt();
            long tar = sc.nextInt();
            long d = sc.nextLong();
            int type = sc.nextInt();

            Node s = g.map.get(src);
            if(s == null) {
                s = new Node(src);
                g.map.put(src, s);
            }

            Node t = g.map.get(tar);
            if(t == null) {
                t = new Node(tar);
                g.map.put(tar, t);
            }

            s.wayMap.put(new Way(d, type), t);

            if(src == 1) {
                g.start = s;
            }

            if(tar == 1) {
                g.start = t;
            }

            if(src == n) {
                g.end = s;
            }

            if(tar == n) {
                g.end = t;
            }
        }

        if(g.start == null || g.end == null) {
            System.out.println(0);
        }

        double t1 = bfs(g, v1, false);
        double t2 = bfs(g, v2, true);

        if(Math.abs(t1 - t2) < 0.001) {
            System.out.println(0);
        } else {
            System.out.println(t1 < t2 ? "1" : "-1");
        }
    }

    private static double bfs(Graph g, long speed, boolean water) {
        Map<Long, Long> vis = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        Queue<Long> wayQueue = new LinkedList<>();

        queue.offer(g.start);
        wayQueue.offer(0L);

        vis.put(g.start.id, 0L);

        while (!queue.isEmpty()) {
            Node n = queue.poll();
            long w = wayQueue.poll();

            n.wayMap.forEach((way, nd) -> {
                if(!water && way.type == 1) {
                    return;
                }

                Long before = vis.get(nd.id);
                if(before != null && w + way.len >= before) {
                    return;
                }

                vis.put(nd.id, w + way.len);
                queue.offer(nd);
                wayQueue.offer(w + way.len);
            });
        }

        Long ans = vis.get(g.end.id);
        if(ans == null) {
            ans = Long.MAX_VALUE;
        }

        return (double) ans / speed;
    }

}

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];
    }
}

#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge{ int from, to, dist, type; };
struct HeapNode
{
    int u;
    long d;
    bool operator<(const HeapNode& rhs) const 
    {
        return d>=rhs.d;
    }
};
vector<Edge> edges;

// flag=true表示可走水路
int dijskra(vector<vector<int>>& G, int s, int t, bool flag)
{
    int n = G.size()-1;
    vector<bool> visited(n+1, false);
    vector<long> d(n+1, INT_MAX);
    priority_queue<HeapNode> Q;
    d[s] = 0;
    Q.push((HeapNode){s,0});
    while (!Q.empty())
    {
        int u = Q.top().u;
        Q.pop();
        if (u==t) break;
        if (visited[u]) continue;
        visited[u] = true;
        int num = G[u].size();
        for (int i = 0; i < num; ++i)
        {
            Edge& e = edges[G[u][i]];
            if (!flag && e.type==1) continue;
            if (d[u]+e.dist < d[e.to] && !visited[e.to])
            {
                d[e.to] = d[u]+e.dist;
                Q.push((HeapNode){e.to, d[e.to]});
            }
        }
    }
    return d[t];
}

int main()
{
    int n, m, v1, v2;
    scanf("%d%d%d%d", &v1,&v2,&n,&m);
    vector<vector<int>> G(n+1);
    for (int i = 0; i < m; ++i)
    {
        int from, to, dist, type;
        scanf("%d%d%d%d", &from, &to, &dist, &type);
        edges.push_back((Edge){from, to, dist, type});
        G[from].push_back(edges.size()-1);
        edges.push_back((Edge){to, from, dist, type});
        G[to].push_back(edges.size()-1);
    }
    double dist1 = dijskra(G,1,n,false);  // 兔子的最短路径
    double dist2 = dijskra(G,1,n,true);   // 乌龟的最短路径
    int result = 0;
    if (dist1/v1 < dist2/v2)
        result = 1;
    else if (dist1/v1 > dist2/v2)
        result = -1;
    printf("%d\n", result);

    return 0;
}

import heapq
import math

# 看了B站灯神的BFS第三讲做的，用例通过90%，还有一个代码输入的地方报错，怀疑是测试用例有问题
class Solution(object):
    def main(self):
        while True:
            ins = input()
            if ins == 'end':
                break
            else:
                v1, v2 = map(int, ins.strip().split(' '))
                n, m = map(int, input().strip().split(' '))

                graph = {}
                for i in range(m):
                    lst = list(map(int, input().strip().split(' ')))
                    if lst[0] not in graph:
                        graph[lst[0]] = {lst[1]: (lst[2], lst[3])}
                    else:
                        graph[lst[0]][lst[1]] = (lst[2], lst[3])
                    if lst[1] not in graph:
                        graph[lst[1]] = {lst[0]: (lst[2], lst[3])}
                    else:
                        graph[lst[1]][lst[0]] = (lst[2], lst[3])

                distance_g = self.dijkstra(graph, 1, False)
                distance_t = self.dijkstra(graph, 1, True)
                g = distance_g[n] / v2
                t = distance_t[n] / v1
                if g > t:
                    print(1)
                elif g == t:
                    print(0)
                else:
                    print(-1)

    def dijkstra(self, graph, s, flag):
        pqueue = []
        heapq.heappush(pqueue, (0, s))
        seen = set()
        distance = self.inin_distance(graph, s)

        while pqueue:
            pair = heapq.heappop(pqueue)
            dist = pair[0]
            node = pair[1]
            seen.add(node)
            nodes = graph[node].keys()

            for w in nodes:
                if w not in seen:
                    if flag and graph[node][w][1] == 1:
                        continue
                    if graph[node][w][0] + dist < distance[w]:
                        heapq.heappush(pqueue, (graph[node][w][0] + dist, w))
                        distance[w] = graph[node][w][0] + dist

        return distance

    def inin_distance(self, graph, s):
        distance = {}
        for node in graph:
            if node != s:
                distance[node] = math.inf
        return distance


Solution().main()

80％C ++，没用longlong的原因，我感觉是

#include <iostream>
#include <queue>
#include <sstream>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;

const int N = 1e4 + 10;
const int M = 1e6 + 10;

int n, m;
typedef pair<int, int> PII;
int v1, v2;

class D
{
public:

    void init()
    {
        //int h[N], e[M], ne[M], w[M], idx;
        memset(h, -1, sizeof h);
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        memset(w, 0, sizeof w);
        //static int idx = 0;
    }
    void add(int a, int b, int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    int djkstra(int n)
    {

        memset(dis, 0x3f, sizeof(dis));
        memset(st, false, sizeof st);
        dis[1] = 0;

        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({ 0, 1 });
        while (heap.size())
        {
            auto  t = heap.top();
            heap.pop();
            int ver = t.second;
            int distance = t.first;

            if (st[ver]) continue;

            st[ver] = true;
            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dis[j] > distance + w[i])
                {
                    dis[j] = distance + w[i];
                    heap.push({ dis[j], j });
                }
            }
        }
        return dis[n];

    }
private:
    int dis[N];
    int h[N], e[M], ne[M], w[M], idx = 0;
    bool st[N];
};


int string_to_int(string s){
    stringstream ss;
    ss << s;
    int foo;
    ss >> foo;
    return foo;
}


int main()
{
    cin >> v1 >> v2;
    cin >> n >> m;
    string str;
    D d1; // 兔子
    D d2; //鬼
    d1.init();
    d2.init();
    while (cin >> str, str[0] != 'e')
    {
        int a = string_to_int(str);
        int b, c, d;
        scanf("%d%d%d", &b, &c, &d);
        if (d == 1)
        {
            d2.add(a, b, c);
        }
        else
        {
            d1.add(a, b, c);
            d2.add(a, b, c);
        }
    }
    int t1 = d1.djkstra(n);
    int t2 = d2.djkstra(n);
    //cout << t1 << " " << t2 << endl;
    if (t1*v2 < t2*v1 ) puts("1");
    else if (t1*v2 == t2*v1) puts("0");
    else puts("-1");

}

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 10010;
const int INF = 0x7fffffff;
const double exps = 1e-9;

struct Edge{
    int from, to, dist;
    Edge(int _from, int _to, int _dist):from(_from), to(_to), dist(_dist){}
};

class Dijkstra{
public:
    struct node{
        int d, u;
        node(int _d, int _u):d(_d), u(_u){}
        bool operator < (const node& rhs) const{
            return d > rhs.d;
        }
    };
    int n, m;
    vector <Edge> edges;
    vector <int> g[MAXN];
    int dis[MAXN];
    bool vis[MAXN];
    Dijkstra(int _n, int _m):n(_n), m(_m){
        for (int i = 0; i <= n; i++){
            g[i].clear();
        }
        edges.clear();
    }
    void addEdge(int from, int to, int dist){
        edges.push_back(Edge(from, to, dist));
        edges.push_back(Edge(to, from, dist));
        g[from].push_back((int)edges.size() - 2);
        g[to].push_back((int)edges.size() - 1);
    }
    int dijkstra(int s, int t){
        priority_queue <node> q;
        for (int i = 0; i <= n; i++){
            dis[i] = INF;
        }
        memset(vis, false, sizeof(vis));
        dis[s] = 0;
        q.push(node(0, s));
        while(!q.empty()){
            node x = q.top();
            q.pop();
            int u = x.u;
            if(vis[u]){
                continue;
            }
            vis[u] = true;
            for (int i = 0; i < g[u].size(); i++){
                Edge& e = edges[g[u][i]];
                if(dis[e.to] > dis[u] + e.dist){
                    dis[e.to] = dis[u] + e.dist;
                    q.push(node(dis[e.to], e.to));
                }
            }
        }
        return dis[t];
    }
};

int string_to_int(string s){
    stringstream ss;
    ss << s;
    int foo;
    ss >> foo;
    return foo;
}

signed main(){
    int v1, v2;
    int n, m;
    scanf("%lld %lld", &v1, &v2);
    scanf("%lld %lld", &n, &m);
    Dijkstra d1(n, m);
    Dijkstra d2(n, m);
    string s;
    int a, b, c, d;
    while(cin >> s){
        if(s == "end"){
            break;
        }
        a = string_to_int(s);
        scanf("%lld %lld %lld", &b, &c, &d);
        if(d == 0){
            d1.addEdge(a, b, c);
        }
        d2.addEdge(a, b, c);
    }
    int f = d1.dijkstra(1, n) * v2;
    int e = d2.dijkstra(1, n) * v1;
    if(f > e) cout << "-1" << "\n";
    else if(f < e) cout << "1" << '\n';
    else cout << "0" << "\n";
    return 0;
}

# include<iostream>
# include<vector>
# include<utility>

# define INFTY 1000000000

using namespace std;

double Dijstra(vector<vector<double>>);
double Dijstra_rabbit(vector<vector<double>>, vector<vector<int>>);

int main(){
	double v_rabbit, v_turtle;
    while(cin>>v_rabbit>>v_turtle){
        int node_num, road_num;
        cin>>node_num>>road_num;
        vector<vector<double>> dist(node_num, vector<double>(node_num, -1));
        vector<vector<int>> type(node_num, vector<int>(node_num, 0));
        
        for(int i = 0; i < node_num; i++)
            dist[i][i] = 0;
        for(int i = 0; i < road_num; i++){
            int a, b, d;
            double c;
            cin>>a>>b>>c>>d;
            dist[a - 1][b - 1] = c; dist[b - 1][a - 1] = c;
            type[a - 1][b - 1] = d; type[b - 1][a - 1] = d;
        }
        string endstr;
        cin>>endstr;
        //求最短路径
        double d_turtle = Dijstra(dist);
        double d_rabbit = Dijstra_rabbit(dist, type);
        double time_turtle = d_turtle / v_turtle;
        double time_rabbit = d_rabbit / v_rabbit;
        
        if(time_turtle < time_rabbit)
            cout<< -1<<endl;
        else if(time_turtle > time_rabbit)
            cout<< 1<<endl;
        else
            cout<<0<<endl;
    }
    return 0;
}

double Dijstra(vector<vector<double>> dist){
    //乌龟
    int n = dist.size();
    vector<bool> visit(n, false);
    vector<double> d(n, INFTY);
    d[0] = 0;
    while(true){
        double mindist = INFTY;
        int u = 0;
        for(int i = 0; i < n; i++){
            if(!visit[i] && d[i] < mindist){
                u =  i;
                mindist = d[i];
            }
        }
        if(mindist == INFTY)
            break;
        visit[u] = true;
        for(int v = 0; v < n; v++){
            if(!visit[v] && dist[u][v] != -1)
                d[v] = min(dist[u][v] + d[u], d[v]);
        }
    }
    return d[n - 1];
}

double Dijstra_rabbit(vector<vector<double>> dist, vector<vector<int>> type){
    int n = dist.size();
    vector<bool> visit(n, false);
    vector<double> d(n, INFTY);
    d[0] = 0;
    while(true){
        double mindist = INFTY;
        int u = 0;
        for(int i = 0; i < n; i++){
            if(!visit[i] && d[i] < mindist){
                u =  i;
                mindist = d[i];
            }
        }
        if(mindist == INFTY)
            break;
        visit[u] = true;
        for(int v = 0; v < n; v++){
            if(!visit[v] && dist[u][v] != -1 && type[u][v] == 0)
                d[v] = min(dist[u][v] + d[u], d[v]);
        }
    }
    return d[n - 1];
}