結果

問題 No.614 壊れたキャンパス
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2017-12-14 14:38:56
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,799 bytes
記録
コンパイル時間 3,361 ms
コンパイル使用メモリ 85,020 KB
実行使用メモリ 229,444 KB
最終ジャッジ日時 2024-12-14 12:47:54
合計ジャッジ時間 30,382 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.*;
import java.util.*;


class P implements Comparable<P>{
    long a,b;
    P(long x,long y){a=x;b=y;}
    @Override
    public int compareTo(P o){
        return Long.compare(a,o.a);
    }
}
class Main {
    static final long I=1L<<53;
    static Map<Long,Integer>bank=new HashMap<Long,Integer>();
    static ArrayList<Long>[]sky;
    static int regist(int a,int b){
        long v=(long)a<<32|b;
        Integer c=bank.get(v);
        if(c!=null)return c;
        int s=bank.size();
        bank.put(v,s);
        sky[a].add((long)b<<32|s);
        return s;
    }
    static ArrayList<Long>[]g;
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int n=sc.nextInt();
        int m=sc.nextInt();
        int k=sc.nextInt();
        int s=sc.nextInt();
        int t=sc.nextInt();
        sky=new ArrayList[n];
        Arrays.setAll(sky,x->new ArrayList<Long>());
        int[]ds=new int[m],es=new int[m];
        for(int i=0;i<m;++i){
            int a=sc.nextInt()-1;
            int b=sc.nextInt();
            int c=sc.nextInt();
            int d=regist(a,b);
            int e=regist(a+1,c);
            ds[i]=d;
            es[i]=e;
        }
        int si=regist(0,s);
        int ti=regist(n-1,t);
        int gs=bank.size();
        g=new ArrayList[gs];
        Arrays.setAll(g,x->new ArrayList<Long>());
        for(int i=0;i<n;++i){
            Collections.sort(sky[i]);
            for(int j=0;j<sky[i].size()-1;++j){
                long vvh=sky[i].get(j);
                int v=(int)vvh;
                int vh=(int)(vvh>>>32);
                long wwh=sky[i].get(j+1);
                int w=(int)wwh;
                int wh=(int)(wwh>>>32);
                g[v].add((long)w<<32|(wh-vh));
                g[w].add((long)v<<32|(wh-vh));
            }
        }
        for(int i=0;i<m;++i)g[ds[i]].add((long)es[i]<<32|0);
        long[]dis=new long[gs];
        Arrays.fill(dis,I);
        Queue<P>q=new PriorityQueue<P>();
        q.add(new P(0,si));
        while(q.size()>0){
            P dw=q.poll();
            long d=dw.a;
            int v=(int)dw.b;
            if(dis[v]<=d)continue;
            dis[v]=d;
            for(long e:g[v]){
                int w=(int)(e>>>32);
                long nd=d+(int)e;
                if(dis[w]<=nd)continue;
                q.add(new P(nd,w));
            }
        }
        out.println(dis[ti]==I?-1:dis[ti]);
        out.close();
    }
    // http://codeforces.com/blog/entry/7018
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
0