結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 16:14:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 2,313 bytes |
コンパイル時間 | 3,680 ms |
コンパイル使用メモリ | 224,968 KB |
実行使用メモリ | 22,496 KB |
最終ジャッジ日時 | 2025-01-25 23:50:47 |
合計ジャッジ時間 | 15,704 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge13 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using mint = modint998244353;//using mint = modint1000000007;using ll = long long;ll INF = 2e18;template<typename T> using vc = vector<T>;template<typename T> using vv = vc<vc<T>>;using vi = vc<int>; using vvi = vv<int>;using vl = vc<ll>; using vvl = vv<ll>;using vs = vc<string>; using vvs = vv<string>;using vb = vc<bool>; using vvb = vv<bool>;using vmint = vc<mint>; using vvmint = vv<mint>;#define rep(i,n) for(ll i=0; i<(n); i++)#define drep(i,n) for(ll i=(n)-1; i>=0; i--)#define rrep(i,n) for(ll i=1; i<=(n); i++)#define nfor(i,a,b) for(ll i=a;i<b;i++)#define dfor(i,a,b) for(ll i=(a)-1; i>=(b); i--)template<class T>istream& operator>>(istream& i, vc<T>& v) {rep(j,(ll) size(v))i >> v[j]; return i; }#define nall(a) a.begin(),a.end()#define rall(a) a.rbegin(),a.rend()#define chmax(x,y) x = max(x,y)#define chmin(x,y) x = min(x,y)#define YES cout<<"Yes"<<endl#define NO cout<<"No"<<endl#define YN {YES;}else{NO;}#define ERROR cout<<-1<<endlvoid print(long double x){ printf("%.20Lf\n",x);}#define vc_cout(v){ll n = size(v);rep(i,n)cout<<v[i]<<endl;}#define vv_cout(v){ll n = size(v);rep(i,n){rep(j,size(v[i])){cout<<' '<<v[i][j];}cout<<endl;}}using Pair = pair<ll,ll>;int main(){ll N, M, P, Y;cin >> N >> M >> P >> Y;vv<Pair> edge(N);rep(i,M) {ll a, b, c;cin >> a >> b >> c;a--,b--;edge[a].push_back({b,c});edge[b].push_back({a,c});}vl cost(N);rep(i,P) {ll d, e;cin >> d >> e;cost[d-1] = e;}vl distances(N,INF);distances[0] = 0;priority_queue<Pair,vc<Pair>,greater<Pair>> pq;pq.push({0,0});while(pq.size()>0) {ll distance = pq.top().first;ll from = pq.top().second;pq.pop();if (distance != distances[from]) continue;for (auto e : edge[from]) {ll d = e.second + distance;if (d<distances[e.first]) {pq.push({d,e.first});distances[e.first] = d;}}}ll ans = 0;rep(i,N) {if (cost[i] == 0) continue;ll cnt = (Y-distances[i])/cost[i];chmax(ans,cnt);}cout << ans << endl;}