結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2015-03-04 00:52:08 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,081 bytes |
コンパイル時間 | 3,761 ms |
コンパイル使用メモリ | 116,704 KB |
実行使用メモリ | 30,924 KB |
最終ジャッジ日時 | 2024-06-24 01:19:47 |
合計ジャッジ時間 | 3,860 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 7 WA * 19 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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[G]=0; SH.Push(new Pair(G,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=S; while(now!=G){ L.Add(now); now=prev[now]; } L.Add(now); var AA=L.ToArray(); 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; } } }