結果

問題 No.2387 Yokan Factory
ユーザー fgwiebfaoishfgwiebfaoish
提出日時 2023-07-21 23:57:20
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,554 ms / 5,000 ms
コード長 10,095 bytes
コンパイル時間 1,275 ms
コンパイル使用メモリ 116,552 KB
実行使用メモリ 60,964 KB
最終ジャッジ日時 2023-10-21 23:54:52
合計ジャッジ時間 15,689 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
24,664 KB
testcase_01 AC 29 ms
24,664 KB
testcase_02 AC 30 ms
24,664 KB
testcase_03 AC 30 ms
24,664 KB
testcase_04 AC 29 ms
24,664 KB
testcase_05 AC 30 ms
24,664 KB
testcase_06 AC 30 ms
24,664 KB
testcase_07 AC 30 ms
24,664 KB
testcase_08 AC 30 ms
24,664 KB
testcase_09 AC 30 ms
24,664 KB
testcase_10 AC 30 ms
24,664 KB
testcase_11 AC 29 ms
24,664 KB
testcase_12 AC 30 ms
24,664 KB
testcase_13 AC 29 ms
24,664 KB
testcase_14 AC 29 ms
24,664 KB
testcase_15 AC 554 ms
55,756 KB
testcase_16 AC 336 ms
55,772 KB
testcase_17 AC 1,290 ms
60,964 KB
testcase_18 AC 850 ms
59,796 KB
testcase_19 AC 969 ms
55,200 KB
testcase_20 AC 769 ms
54,032 KB
testcase_21 AC 1,542 ms
57,884 KB
testcase_22 AC 719 ms
55,076 KB
testcase_23 AC 1,085 ms
55,836 KB
testcase_24 AC 431 ms
46,848 KB
testcase_25 AC 688 ms
51,504 KB
testcase_26 AC 1,313 ms
57,164 KB
testcase_27 AC 1,554 ms
59,516 KB
testcase_28 AC 33 ms
24,672 KB
testcase_29 AC 36 ms
26,720 KB
testcase_30 AC 35 ms
24,672 KB
testcase_31 AC 33 ms
24,672 KB
testcase_32 AC 32 ms
24,672 KB
testcase_33 AC 32 ms
24,672 KB
testcase_34 AC 37 ms
26,720 KB
testcase_35 AC 35 ms
24,672 KB
testcase_36 AC 32 ms
24,672 KB
testcase_37 AC 30 ms
24,672 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
static class Program {
	const long inf = long.MaxValue>>1;
	const int mod = 998244353;
	static Sc sc = new Sc();
	static void Main() {
		Pt pt = new Pt(Solve);
		pt.Sm();
	}
	static void Solve(Pt pt) {
		var (n, m, x)=sc.Tp3<long>();
		var li = new List<(int v, int d,int h)>[n+1];
		for(int i = 1;i<=n;i++) {
			li[i]=new List<(int, int, int)>();
		}
		for(int i = 0;i<m;i++) {
			var e = sc.Ia;
			li[e[0]].Add((e[1], e[2], e[3]));
			li[e[1]].Add((e[0], e[2], e[3]));
		}
		long lb = -1, ub = int.MaxValue, mid = 0;
		while(lb+1!=ub) {
			mid=(ub+lb)/2;
			if(Fu(mid)) { lb=mid; }
			else { ub=mid; }
		}
		bool Fu(long p) {
			var b = new bool[n+1];
			var c = new long[n+1];
			for(int i = 1;i<=n;i++) { c[i]=inf; }
			var pq = new Rheap<int>(32);
			pq.Push(new Rheap<int>.Dt(0,1));
			while(pq.cnt>0) {
				var e = pq.Dequeue;
				if(b[e.d]) { continue; }
				b[e.d]=true;
				for(int i = 0;i<li[e.d].Count;i++) {
					if(li[e.d][i].h<p) continue;
					if(!b[li[e.d][i].v]&&c[li[e.d][i].v]>li[e.d][i].d+e.n) {
						pq.Push(new Rheap<int>.Dt(li[e.d][i].d+e.n,li[e.d][i].v));
						c[li[e.d][i].v]=li[e.d][i].d+e.n;
					}
				}
			}
			return c[n]<=x;
		}
		pt.Wl(lb);
	}
}
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 void Push(long n,T d) {
		int a = n!=la ? Bsr(la^n)+1 : 0;
		if(h[a]==bf[a].Length) { Extend(a); }
		bf[a][h[a]]=new Dt(n,d);
		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) { n+=1; }
		return n;
	}
}
public class Pt {
	private StringBuilder sb = new StringBuilder();
	public Pt(Action<Pt> f) { f(this); }
	public void W(int s) { sb.Append(s); }
	public void W(long s) { sb.Append(s); }
	public void W(double s) { sb.Append(s); }
	public void W(decimal s) { sb.Append(s); }
	public void W(char s) { sb.Append(s); }
	public void W(string s) { sb.Append(s); }
	public void W(object s) { sb.Append(s); }
	public void W(params object[] s) { sb.Append(string.Join(" ",s)); }
	public void Wl(int s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(long s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(double s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(decimal s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(char s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(string s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(object s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(int[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(long[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(double[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(string[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(params object[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl() { sb.Append(Environment.NewLine); }
	public void Sm() { Console.Write(sb); }
	public void Op(StreamWriter sw) {
		sw.Write(sb);
		sw.Close();
	}
	public static bool operator ==(Pt a,Pt b) { return a.sb.ToString()==b.sb.ToString(); }
	public static bool operator !=(Pt a,Pt b) { return a.sb.ToString()!=b.sb.ToString(); }
	public override bool Equals(object obj) { return false; }
	public override int GetHashCode() { return 0; }
}
public class Sc {
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string Rl() { return Console.ReadLine(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string[] Sp(string st) { return st.Split(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	private T Ct<T>(string s) { return (T)Convert.ChangeType(s,typeof(T)); }
	public virtual int I { get { return int.Parse(Rl()); } }
	public virtual long L { get { return long.Parse(Rl()); } }
	public virtual double D { get { return double.Parse(Rl()); } }
	public virtual string S { get { return Rl(); } }
	public int[] Ia { get { return Array.ConvertAll(Sp(Rl()),int.Parse); } }
	public long[] La { get { return Array.ConvertAll(Sp(Rl()),long.Parse); } }
	public double[] Da { get { return Array.ConvertAll(Sp(Rl()),double.Parse); } }
	public string[] Sa { get { return Sp(Rl()); } }
	public object[] Oa { get { return Sp(Rl()); } }
	public int[] Ia2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse); } }
	public int[] Ia3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),int.Parse); }
	public int[] Ia3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse); }
	public long[] La2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse); } }
	public long[] La3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),long.Parse); }
	public long[] La3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse); }
	public double[] Da2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse); } }
	public double[] Da3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),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(Sp(Rl())); } 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,Sp(Rl())); } return a; }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T) Tp2<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T) Tp3<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T) Tp4<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T) Tp5<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T, T) Tp6<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4]), Ct<T>(s[5])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T2) Tp2<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T2>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T1, T2) Tp3<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T1>(s[1]), Ct<T2>(s[2])); }
}
public class Scr:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	private bool bo = false;
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string Rl() {
		if(bo) { return li[l++%li.Count]; }
		li.Add(Console.ReadLine());
		return li[li.Count-1];
	}
	public void Again() { bo=true; }
}
public class Sc2:Sc {
	private string[] sps = new string[] { " ","　","\t" };
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string[] Sp(string st) { return st.Split(sps,StringSplitOptions.RemoveEmptyEntries); }
	public override int I { get { return int.Parse(Sp(Rl())[0]); } }
	public override long L { get { return long.Parse(Sp(Rl())[0]); } }
	public override double D { get { return double.Parse(Sp(Rl())[0]); } }
	public override string S { get { return Sp(Rl())[0]; } }
}
public class Sct:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	public void Add(int s) { li.Add(s.ToString()); }
	public void Add(long s) { li.Add(s.ToString()); }
	public void Add(double s) { li.Add(s.ToString()); }
	public void Add(string s) { li.Add(s.ToString()); }
	public void Add(object s) { li.Add(s.ToString()); }
	public void Add(int[] s) { li.Add(string.Join(" ",s)); }
	public void Add(long[] s) { li.Add(string.Join(" ",s)); }
	public void Add(double[] s) { li.Add(string.Join(" ",s)); }
	public void Add(string[] s) { li.Add(string.Join(" ",s)); }
	public void Add(object[] s) { li.Add(string.Join(" ",s)); }
	protected override string Rl() { return li[l++]; }
	public void Clear() { li.Clear(); l=0; }
	public void Again() { l=0; }
	public void Pf() { Console.WriteLine(string.Join("\n",li)); }
}
0