結果

問題 No.1 道のショートカット
ユーザー fgwiebfaoish
提出日時 2020-02-15 02:11:11
言語 C#
(csc 3.4.0-beta4-19569-03)
結果
AC  
実行時間 44 ms
コード長 5,434 Byte
コンパイル時間 960 ms
使用メモリ 19,196 KB
最終ジャッジ日時 2020-02-15 02:11:17

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 28 ms
17,636 KB
02.txt AC 28 ms
17,952 KB
03.txt AC 28 ms
17,808 KB
04.txt AC 28 ms
17,692 KB
05.txt AC 36 ms
18,944 KB
06.txt AC 36 ms
18,556 KB
07.txt AC 32 ms
18,828 KB
08.txt AC 36 ms
18,764 KB
09.txt AC 36 ms
19,192 KB
10.txt AC 36 ms
18,908 KB
99_system_test1.txt AC 28 ms
17,900 KB
99_system_test2.txt AC 28 ms
17,668 KB
99_system_test3.txt AC 32 ms
18,336 KB
challenge01.txt AC 28 ms
17,660 KB
challenge02.txt AC 28 ms
17,728 KB
challenge03.txt AC 36 ms
18,412 KB
challenge04.txt AC 32 ms
18,364 KB
challenge05.txt AC 28 ms
17,672 KB
challenge06.txt AC 44 ms
18,788 KB
challenge07.txt AC 32 ms
18,936 KB
challenge08.txt AC 32 ms
18,380 KB
challenge09.txt AC 32 ms
18,472 KB
challenge10.txt AC 36 ms
18,736 KB
system_test1.txt AC 28 ms
17,636 KB
system_test2.txt AC 36 ms
19,196 KB
system_test3.txt AC 32 ms
18,332 KB
system_test4.txt AC 32 ms
18,604 KB
system_test5.txt AC 36 ms
18,880 KB
system_test6.txt AC 32 ms
18,492 KB
system_test7.txt AC 36 ms
18,792 KB
system_test8.txt AC 36 ms
18,804 KB
system_test9.txt AC 32 ms
18,988 KB
system_test10.txt AC 36 ms
18,796 KB
system_test11.txt AC 28 ms
18,104 KB
system_test12.txt AC 32 ms
18,504 KB
system_test13.txt AC 32 ms
18,604 KB
system_test14.txt AC 32 ms
18,308 KB
system_test15.txt AC 24 ms
17,792 KB
system_test16.txt AC 24 ms
17,996 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.4.0-beta4-19569-03 (82f2e254)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static List<Tuple<int,int,int>>[] li;
	static bool[] b;
	static void Main(){
		Sc sc=new Sc();
		int n=sc.I;
		int d=sc.I;
		int m=sc.I;
		li=new List<Tuple<int,int,int>>[n+1];
		b=new bool[n+1];
		var c=new long[n+1];
		var g=new long[n+1];
		for(int i=1;i<=n;i++){
			li[i]=new List<Tuple<int,int,int>>();
			c[i]=long.MaxValue;
			g[i]=long.MaxValue;
		}
		var sa=sc.Ia;
		var ta=sc.Ia;
		var ya=sc.Ia;
		var ma=sc.Ia;
		for(int i=0;i<m;i++){
			li[sa[i]].Add(Tuple.Create(ta[i],ma[i],ya[i]));
		}
		var pq=new Rheap<Tuple<int,int>>(32);
		pq.Push(new Rheap<Tuple<int,int>>.Dt(0,Tuple.Create(1,0)));
		while(pq.cnt>0){
			var e=pq.Dequeue;
			if(g[e.d.Item1]<=e.d.Item2){continue;}
			g[e.d.Item1]=e.d.Item2;
			b[e.d.Item1]=true;
			for(int i=0;i<li[e.d.Item1].Count;i++){
				if(e.d.Item2+li[e.d.Item1][i].Item3>d){continue;}
				if(!b[li[e.d.Item1][i].Item1]&&c[li[e.d.Item1][i].Item1]>li[e.d.Item1][i].Item2+e.n){
					pq.Push(new Rheap<Tuple<int,int>>.Dt(li[e.d.Item1][i].Item2+e.n,Tuple.Create(li[e.d.Item1][i].Item1,e.d.Item2+li[e.d.Item1][i].Item3)));
					c[li[e.d.Item1][i].Item1]=li[e.d.Item1][i].Item2+e.n;
				}
				else if(g[li[e.d.Item1][i].Item1]>e.d.Item2+li[e.d.Item1][i].Item3){
					pq.Push(new Rheap<Tuple<int,int>>.Dt(li[e.d.Item1][i].Item2+e.n,Tuple.Create(li[e.d.Item1][i].Item1,e.d.Item2+li[e.d.Item1][i].Item3)));
				}
			}
		}
		
		Console.WriteLine("{0}",c[n]==long.MaxValue?-1:c[n]);
	}
}
public class Rheap<T>{
	public class Dt{
		public long n;
		public T d;
		public Dt(long n,T d){this.n=n;this.d=d;}
		public override string ToString()=>"d:"+d.ToString()+" n:"+n.ToString();
	}
	private const int m=65;
	private long la=0;
	private Dt[][] bf;
	private int[] h;
	public int cnt=0;
	public Rheap(int max){
		bf=new Dt[m][];
		h=new int[m];
		for(int i = 0;i<m;i++) {bf[i]=new Dt[max];}
	}
	public void Push(Dt x){
		int a=x.n!=la?Bsr(la^x.n)+1:0;
		if(h[a]==bf[a].Length){Extend(a);}
		bf[a][h[a]]=x;
		cnt++;
		h[a]++;
	}
	public Dt Peek{get{
		if(h[0]==0){
			for(int i = 1;i<m;i++) {
				if(h[i]>0){
					int p=0;
					for(int j = 1;j<h[i];j++) {
						if(bf[i][p].n>bf[i][j].n){p=j;}
					}
					la=bf[i][p].n;
					for(int j = 0;j<h[i];j++) {
						Push(bf[i][j]);
						cnt--;
					}
					h[i]=0;
					break;
				}
			}
		}
		return bf[0][h[0]-1];
	}}
	public Dt Dequeue{get{
		var e=Peek;
		h[0]--;
		cnt--;
		return e;
	}}
	private void Extend(int n){
		var nhe=new Dt[bf[n].Length<<1];
		Array.Copy(bf[n],nhe,bf[n].Length);
		bf[n]=nhe;
	}
	private int Bsr(long b){
		int n=0;
		if(b==0){return -1;}
		if((b&-4294967296)!=0){b=b&-4294967296;n+=32;}
		if((b&-281470681808896)!=0){b=b&-281470681808896;n+=16;}
		if((b&-71777214294589696)!=0){b=b&-71777214294589696;n+=8;}
		if((b&-1085102592571150096)!=0){b=b&-1085102592571150096;n+=4;}
		if((b&-3689348814741910324)!=0){b=b&-3689348814741910324;n+=2;}
		if((b&-6148914691236517206)!=0){b=b&-6148914691236517206;n+=1;}
		return n;
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}
0