제출 #1257537

#제출 시각아이디문제언어결과실행 시간메모리
1257537lftroqConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
3 ms4936 KiB
#include<bits/stdc++.h> #define endl '\n' #define fi first #define se second using namespace std; typedef long double ld; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> llll; typedef pair<ld,ld> ldld; const int N=2e5+5; int n,m,s,t,l; vector<pii> graph[N]; ll d[2][N]; void dijkstra(int u,int k) { for(int i=1;i<=n;i++) d[k][i]=1e16; d[k][u]=0; priority_queue<llll,vector<llll>,greater<llll>> pq; pq.push({d[k][u],u}); while((int)pq.size()) { ll temp=pq.top().fi; int u=pq.top().se; pq.pop(); if(d[k][u]!=temp) continue; for(int i=0;i<(int)graph[u].size();i++) { int v=graph[u][i].fi,w=graph[u][i].se; if(d[k][v]>d[k][u]+w) { d[k][v]=d[k][u]+w; pq.push({d[k][v],v}); } } } } void solve() { ll k; cin >> n >> m >> s >> t >> l >> k; for(int i=1;i<=m;i++) { int u,v,w; cin >> u >> v >> w; graph[u].push_back({v,w}); graph[v].push_back({u,w}); } dijkstra(s,0); if(d[0][t]<=k) { cout << n*(n-1ll)/2 << endl; return; } dijkstra(t,1); vector<int> v; for(int i=1;i<=n;i++) v.push_back(d[1][i]); sort(v.begin(),v.end()); ll ans=0; for(int i=1;i<=n;i++) { int l=1,r=n,liem=0; while(l<=r) { int mid=(l+r)>>1; if(d[0][i]+l+v[mid-1]<=k) { liem=mid; l=mid+1; } else r=mid-1; } //cout << i << ": " << d[0][i] << ' ' << d[1][i] << " " << liem << endl; ans+=liem; } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if(fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } int t=1; //cin >> t; while(t--) solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...