#893935 (C++17) No.2387 Yokan Factory

• 問題: No.2387 Yokan Factory
• ユーザー: k82b
• 提出日時: 2023-07-21 21:55:48
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 377 ms / 5,000 ms
• コード長: 937 bytes
• コンパイル時間: 1,202 ms
• コンパイル使用メモリ: 84,260 KB
• 実行使用メモリ: 11,632 KB
• 最終ジャッジ日時: 2023-10-21 21:56:36
• 合計ジャッジ時間: 5,381 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 7,076 KB
testcase_01	AC	3 ms; 7,076 KB
testcase_02	AC	3 ms; 7,076 KB
testcase_03	AC	3 ms; 7,080 KB
testcase_04	AC	3 ms; 7,080 KB
testcase_05	AC	3 ms; 7,080 KB
testcase_06	AC	3 ms; 7,080 KB
testcase_07	AC	3 ms; 7,080 KB
testcase_08	AC	3 ms; 7,080 KB
testcase_09	AC	3 ms; 7,080 KB
testcase_10	AC	3 ms; 7,076 KB
testcase_11	AC	3 ms; 7,076 KB
testcase_12	AC	3 ms; 7,076 KB
testcase_13	AC	3 ms; 7,076 KB
testcase_14	AC	3 ms; 7,076 KB
testcase_15	AC	233 ms; 11,632 KB
testcase_16	AC	174 ms; 11,260 KB
testcase_17	AC	346 ms; 11,260 KB
testcase_18	AC	377 ms; 10,864 KB
testcase_19	AC	184 ms; 9,832 KB
testcase_20	AC	125 ms; 9,576 KB
testcase_21	AC	375 ms; 10,624 KB
testcase_22	AC	128 ms; 9,364 KB
testcase_23	AC	319 ms; 9,800 KB
testcase_24	AC	120 ms; 9,500 KB
testcase_25	AC	109 ms; 8,732 KB
testcase_26	AC	176 ms; 10,144 KB
testcase_27	AC	137 ms; 10,444 KB
testcase_28	AC	5 ms; 7,136 KB
testcase_29	AC	5 ms; 7,164 KB
testcase_30	AC	4 ms; 7,160 KB
testcase_31	AC	5 ms; 7,132 KB
testcase_32	AC	3 ms; 7,108 KB
testcase_33	AC	4 ms; 7,104 KB
testcase_34	AC	5 ms; 7,168 KB
testcase_35	AC	5 ms; 7,152 KB
testcase_36	AC	3 ms; 7,104 KB
testcase_37	AC	2 ms; 7,080 KB

ソースコード

#include<iostream>
#include<vector>
#include<queue>
long N,M,X;
std::vector<std::pair<int,std::pair<int,int>>>G[1<<17];
long dist[1<<17];
std::priority_queue<std::pair<long,int>>Q;
int main()
{
	std::cin>>N>>M>>X;
	for(int i=0;i<M;++i)
	{
		int u,v,a,b;
		std::cin>>u>>v>>a>>b;
		u--,v--;
		G[u].push_back(std::make_pair(v,std::make_pair(a,b)));
		G[v].push_back(std::make_pair(u,std::make_pair(a,b)));
	}
	int L=0,R=1e9+1;
	while(R-L>1)
	{
		int mid=(L+R)/2;
		for(int i=1;i<N;++i)dist[i]=5e18;
		Q.push({0,0});
		while(!Q.empty())
		{
			auto[c,u]=Q.top();Q.pop();
			c=-c;
			if(dist[u]<c)continue;
			for(std::pair<int,std::pair<int,int>>p:G[u])
			{
				int v=p.first;
				auto[a,b]=p.second;
				if(b<mid)continue;
				if(dist[u]+a>X)continue;
				if(dist[v]>dist[u]+a)
				{
					dist[v]=dist[u]+a;
					Q.push({-dist[v],v});
				}
			}
		}
		if(dist[N-1]!=(long)5e18)L=mid;
		else R=mid;
	}
	if(L==0)L=-1;
	std::cout<<L<<"\n";
}