Submission #1963083

---

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;
        int w;
        Edge(int end,int scost,int to,int w){
            this.endPoint=end;
            this.sleepCost=scost;
            this.to=to;
            this.w=w;
        }
    }

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

    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],w[i]));
                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],w[i-1]));
                sleepcost -=w[i-1];
            }
        }

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

        //事前にdis[src]を計算できない!(使えない辺があるから)




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

        int left=0;
        int right=Integer.MAX_VALUE/2;
        while(right-left>1){
            int center = (right+left)/2;
            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]){
                    if(dis[node.v] + e.cost > center)continue;
                    if(dis[node.v] + e.w < dis[e.to]){
                        dis[e.to] = dis[node.v]+e.w;
                        que.add(new QueNode(e.to, dis[e.to]));
                    }
                }
            }
            if(dis[dst] == Integer.MAX_VALUE){
                left = center;
            }else{
                right = center;
            }
        }
        System.out.println(right);
    }
}

Submission Info

Compile Error

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

Judge Result