結果

問題 No.160 最短経路のうち辞書順最小
ユーザー kuuso1
提出日時 2015-03-02 00:10:33
言語 C#(csc)
(csc 3.9.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,102 bytes
コンパイル時間 2,220 ms
コンパイル使用メモリ 115,996 KB
実行使用メモリ 28,624 KB
最終ジャッジ日時 2024-06-24 00:46:33
合計ジャッジ時間 3,048 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 6 WA * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}
class Sol{
    public void Solve(){
        
        int[] prev=new int[N];
        for(int i=0;i<N;i++)prev[i]=-1;
        int[] Tot=new int[N];
        int Inf=(int)(1e9);
        for(int i=0;i<N;i++)Tot[i]=Inf;
        
        SkewHeap<Pair> SH =new SkewHeap<Pair>();
        Tot[S]=0;
        SH.Push(new Pair(S,0));
        bool[] used=new bool[N];
        
        while(SH.Count>0){
            Pair p = SH.Top; SH.Pop();
            if(used[p.Pos])continue;
            used[p.Pos]=true;
            foreach (Pair e in E[p.Pos]) {
                if (Tot[e.Pos] > p.Cost + e.Cost) {
                    Tot[e.Pos] = p.Cost + e.Cost;
                    prev[e.Pos]=p.Pos;
                    SH.Push(new Pair(e.Pos, Tot[e.Pos]));
                }
            }
        }
        
        List<int> L=new List<int>();
        int now=G;
        while(now!=S){
            L.Add(now);
            now=prev[now];
        }
        L.Add(now);
        
        var AA=L.ToArray();
        Array.Reverse(AA);
        Console.WriteLine(String.Join(" ",AA));
        
    }
    int N,M;
    int S,G;
    List<Pair>[] E;
    
    public Sol(){
        var d=ria();
        N=d[0];M=d[1];S=d[2];G=d[3];
        E=new List<Pair>[N];
        for(int i=0;i<N;i++)E[i]=new List<Pair>();
        
        for(int i=0;i<M;i++){
            var dd=ria();
            E[dd[0]].Add(new Pair(dd[1],dd[2]));
            E[dd[1]].Add(new Pair(dd[0],dd[2]));
        }
        for(int i=0;i<N;i++){
            E[i].Sort((x,y)=>x.Pos>y.Pos?1:x.Pos<y.Pos?-1:0);
        }
    }
    
    static String rs(){return Console.ReadLine();}
    static int ri(){return int.Parse(Console.ReadLine());}
    static long rl(){return long.Parse(Console.ReadLine());}
    static double rd(){return double.Parse(Console.ReadLine());}
    static String[] rsa(){return Console.ReadLine().Split(' ');}
    static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
    static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
    static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}
class Pair : IComparable<Pair> {
    public int Pos;
    public int Cost;
    public Pair(int p, int c) {
        Pos = p; Cost = c;
    }
    public int CompareTo(Pair t) {
        //return this.Cost > t.Cost ? -1 : this.Cost < t.Cost ? 1 : 0;
        return this.Cost > t.Cost ? 1 : this.Cost < t.Cost ? -1 : 0;
    }
}
class SkewHeap<T> where T:IComparable<T>{
    public int Count{
        get{return cnt;}
        private set{cnt=value;}
    }
    
    public SkewHeap(){
        root=null;
        this.Count=0;
    }
    
    public void Push(T v){
        NodeSH<T> p=new NodeSH<T>(v);
        root=NodeSH<T>.Meld(root,p);
        this.Count++;
    }
    
    public void Pop(){
        if(root==null)return;
        root=NodeSH<T>.Meld(root.L,root.R);
        this.Count--;
    }
    
    public T Top{
        get{return root.Val;}
    }
    
    int cnt;
    NodeSH<T> root;
    
    class NodeSH<S> where S : IComparable<S> {
        public NodeSH<S> L, R;
        public S Val;
        public NodeSH(S v){
            Val = v;
            L = null; R = null;
        }
        public static NodeSH<S> Meld(NodeSH<S> a, NodeSH<S> b){
            if(a == null)return b;
            if (b == null) return a;
            if (a.Val.CompareTo(b.Val) > 0) swap(ref a, ref b);
            a.R = Meld(a.R, b);
            swap(ref a.L, ref a.R);
            return a;
        }
        static void swap<U>(ref U x, ref U y) {
            U t = x; x = y; y = t;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0