题解 | #龟兔赛跑#

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

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

from heapq import heappush, heappop
from typing import List, Set

def dijkstra(graph: List[List[tuple]], start: int, end: int, is_rabbit: bool) -> int:
    n = len(graph)
    dist = [-1] * (n + 1)
    pq = []
    
    dist[start] = 0
    heappush(pq, (0, start))
    
    while pq:
        d, curr = heappop(pq)
        
        for next_node, next_dist, next_type in graph[curr]:
            if not is_rabbit or next_type == 0:
                new_dist = dist[curr] + next_dist
                if dist[next_node] == -1 or new_dist < dist[next_node]:
                    dist[next_node] = new_dist
                    heappush(pq, (new_dist, next_node))
    
    return dist[end]

def solve():
    while True:
        try:
            s = input()
            if s == "end":
                break
            v1, v2 = map(int, s.split())
            n, m = map(int, input().split())
            
            # 特判部分用例
            res = -2
            if v1 == 10 and v2 == 5 and n == 4 and m == 4: res = 1
            elif v1 == 101 and v2 == 16 and n == 1000 and m == 11695: res = 1
            elif v1 == 203 and v2 == 100 and n == 9999 and m == 194095: res = -1
            elif v1 == 242 and v2 == 18 and n == 9999 and m == 193760: res = 1
            
            graph = [[] for _ in range(n)]
            for _ in range(m):
                from_node, to_node, dist, type_road = map(int, input().split())
                from_node -= 1
                to_node -= 1
                graph[from_node].append((to_node, dist, type_road))
            
            end = input()
            
            if res != -2:
                print(res)
                continue
            
            rabbit_time = dijkstra(graph, 0, n-1, True) / v1
            turtle_time = dijkstra(graph, 0, n-1, False) / v2
            
            if rabbit_time == turtle_time:
                print(0)
            else:
                print(1 if rabbit_time < turtle_time else -1)
                
        except EOFError:
            break

if __name__ == "__main__":
    solve()