제출 #205891

#제출 시각아이디문제언어결과실행 시간메모리
205891mraronCheap flights (LMIO18_pigus_skrydziai)C++14
28 / 100
3083 ms29304 KiB
#include<bits/stdc++.h> using namespace std; int n,m; typedef long long ll; vector<pair<int, ll>> adj[300001]; ll cost(int a, int b) { if(adj[a].size()>adj[b].size()) swap(a,b); auto it=lower_bound(adj[a].begin(),adj[a].end(), make_pair(b,0LL)); if(it==adj[a].end() || it->first!=b) return 0; return it->second; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<m;++i) { int a,b,c; cin>>a>>b>>c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } ll ans=0; for(int i=1;i<=n;++i) { ll cans=0; for(auto j:adj[i]) { cans+=j.second; } ans=max(ans, cans); sort(adj[i].begin(),adj[i].end()); } const int lim=2000; for(int i=1;i<=n;++i) { if(adj[i].size()<=lim) { for(int j=0;j<adj[i].size();++j) { for(int k=j+1;k<adj[i].size();++k) { ans=max(ans, adj[i][j].second+adj[i][k].second+cost(adj[i][j].first, adj[i][k].first)); } } }else { vector<int> kell(n+1); for(auto j:adj[i]) { kell[j.first]=j.second; } for(auto j:adj[i]) { for(auto k:adj[j.first]) { if(kell[k.first]) ans=max(ans, k.second+j.second+kell[k.first]); } } } } cout<<ans<<"\n"; return 0; }

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

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<adj[i].size();++j) {
                ~^~~~~~~~~~~~~~
pigus_skrydziai.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j+1;k<adj[i].size();++k) {
                   ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...