結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー kotatsugame
提出日時 2025-01-25 12:53:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 768 bytes
コンパイル時間 1,016 ms
コンパイル使用メモリ 75,648 KB
実行使用メモリ 19,332 KB
最終ジャッジ日時 2025-01-25 22:25:52
合計ジャッジ時間 7,320 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge8
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:26:21: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   26 |                 auto[d,u]=Q.top();Q.pop();
      |                     ^
main.cpp:29:25: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   29 |                 for(auto[v,c]:G[u])
      |                         ^

ソースコード

diff # 

#include<iostream>
#include<queue>
#include<vector>
#include<cassert>
using namespace std;
int N,M,P;
long Y;
vector<pair<int,int> >G[2<<17];
long D[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>M>>P>>Y;
	for(int i=0;i<M;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
		G[b].push_back(make_pair(a,c));
	}
	for(int i=2;i<=N;i++)D[i]=9e18;
	priority_queue<pair<long,int> >Q;
	Q.push(make_pair(0L,1));
	while(!Q.empty())
	{
		auto[d,u]=Q.top();Q.pop();
		d=-d;
		if(D[u]<d)continue;
		for(auto[v,c]:G[u])
		{
			long nd=d+c;
			if(D[v]>nd)
			{
				D[v]=nd;
				Q.push(make_pair(-nd,v));
			}
		}
	}
	long ans=0;
	for(;P--;)
	{
		int d,e;cin>>d>>e;
		long v=Y-D[d];
		if(v>=0)ans=max(ans,v/e);
	}
	cout<<ans<<endl;
}
0