Submission #1962629

---

Source Code Expand

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main{

    static class Dijkstra{
        class Edge{
            int to,cost;
            Edge(int t,int c){to=t;cost=c;}
        }

        int N;
        List<Edge>[] G;
        
        Dijkstra(int N){
            this.N=N;
            G = new ArrayList[N];
            for(int i=0;i<N;++i)G[i] = new ArrayList<>();
        }

        void addEdge(int from,int to,int cost){
            G[from].add(new Edge(to, cost));
        }

        int[] dijkstra(int s){
            class QueNode{
                int v,w;
                QueNode(int v,int w){this.v=v;this.w=w;}
            }
            int[] dis = new int[N];
            Arrays.fill(dis, Integer.MAX_VALUE);
            dis[s] = 0;
            PriorityQueue<QueNode> que = new PriorityQueue<>((a,b) -> a.w - b.w);
            que.add(new QueNode(s,0));
            while(!que.isEmpty()){
                QueNode node = que.poll();
                if(dis[node.v] < node.w)continue;
                for(Edge e : G[node.v]){
                    if(dis[e.to] > dis[node.v] + e.cost){
                        dis[e.to] = dis[node.v]+e.cost;
                        que.add(new QueNode(e.to, dis[e.to]));
                    }
                }
            }
            return dis;
        }
    }

    static class Edge{
        int cost;
        int sleepCost;
        int endPoint;
        int to;
        Edge(int end,int scost,int to){
            this.endPoint=end;
            this.sleepCost=scost;
            this.to=to;
        }
    }

    static List<Edge>[] edgeList;
    static boolean[] used;

    static boolean dfs(int s,int v,int c){
        used[s]=true;
        if(s==v)return true;
        for(Edge e : edgeList[s]){
            if(e.cost > c)continue;
            if(used[e.to])continue;
            if(dfs(e.to,v,c))return true;
        }
        return false;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int src=scan.nextInt();
        int dst=scan.nextInt();

        Dijkstra djk = new Dijkstra(N);
        edgeList = new ArrayList[N];
        for(int i=0;i<N;++i)edgeList[i] = new ArrayList<>();

        while(M-->0){
            int L = scan.nextInt();
            int[] s = new int[L];
            int[] w = new int[L-1];
            for(int i=0;i<L;++i)s[i] = scan.nextInt();
            for(int i=0;i<L-1;++i)w[i] = scan.nextInt();

            for(int i=0;i<L-1;++i){
                djk.addEdge(s[i], s[i+1], w[i]);
                djk.addEdge(s[i+1], s[i], w[i]);
            }

            int sleepcost=0;
            for(int i=0;i<L-1;++i)sleepcost += w[i];
            for(int i=0;i<L-1;++i){
                edgeList[s[i]].add(new Edge(s[L-1],sleepcost,s[i+1]));
                sleepcost -= w[i];
            }

            sleepcost=0;
            for(int i=0;i<L-1;++i)sleepcost += w[i];
            for(int i=L-1;i>0;--i){
                edgeList[s[i]].add(new Edge(s[0], sleepcost,s[i-1]));
                sleepcost -=w[i-1];
            }
        }

        int[] srcdis = djk.dijkstra(src);
        int[] dstdis = djk.dijkstra(dst);
        for(int i=0;i<N;++i){
            for(Edge e : edgeList[i]){
                e.cost = srcdis[i]+e.sleepCost + dstdis[e.endPoint];
            }
        }

        used = new boolean[N];
        int left=0;
        int right = (int)1e9;
        while(right - left > 1){
            Arrays.fill(used, false);
            int center=(left+right)/2;
            if(dfs(src,dst,center)){
                right = center;
            }else{
                left = center;
            }
        }
        System.out.println(right);

        // class QueNode{
        //     int v,w;
        //     QueNode(int v,int w){this.v=v;this.w=w;}
        // }

        // PriorityQueue<QueNode> que = new PriorityQueue<>((a,b) -> a.w-b.w);
        // int[] dis = new int[N];
        // Arrays.fill(dis, Integer.MAX_VALUE);
        // dis[src] = 0;
        // que.add(new QueNode(src, 0));
        // while(!que.isEmpty()){
        //     QueNode node = que.poll();
        //     if(node.w > dis[node.v])continue;
        //     for(Edge e : edgeList[node.v]){
        //         int cost = Math.max(dis[node.v], e.cost);
        //         if(cost < dis[e.to]){
        //             dis[e.to] = cost;
        //             que.add(new QueNode(e.to, cost));
        //         }
        //     }
        // }
        //System.out.println(dis[dst]);
    }
}

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result