結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-01-25 12:46:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 455 ms / 2,000 ms |
コード長 | 964 bytes |
コンパイル時間 | 7,109 ms |
コンパイル使用メモリ | 333,996 KB |
実行使用メモリ | 22,504 KB |
最終ジャッジ日時 | 2025-01-25 22:21:26 |
合計ジャッジ時間 | 18,133 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using mint=atcoder::modint998244353;#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define int long longtemplate<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;signed main(){int N,M,P,Y;cin>>N>>M>>P>>Y;vector<vector<pair<int,int>>> g(N);for(int i=0;i<M;i++){int a,b,c;cin>>a>>b>>c;a--;b--;g[a].push_back({b,c});g[b].push_back({a,c});}vector<int> v(N,1e18);for(int i=0;i<P;i++){int d,e;cin>>d>>e;v[d-1]=e;}vector<int> dist(N,1e18);dist[0]=0;pqmin<pair<int,int>> pq;pq.push({0,0});while(pq.size()){auto[cost,p]=pq.top();pq.pop();if(dist[p]<cost)continue;for(auto&&[e,c]:g[p]){if(dist[e]>dist[p]+c){dist[e]=dist[p]+c;pq.push({dist[e],e});}}}int ans=0;for(int i=0;i<N;i++){int tmp=max<int>(0,Y-dist[i]);ans=max(ans,tmp/v[i]);}cout<<ans<<endl;}