제출 #256130

#제출 시각아이디문제언어결과실행 시간메모리
256130aloo123Cheap flights (LMIO18_pigus_skrydziai)C++14
28 / 100
3074 ms169908 KiB
#include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <ratio> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #include <climits> #define ll long long #define ld long double #define mp make_pair #define pb push_back #define in insert #define vll vector<ll> #define endl "\n" #define pll pair<ll,ll> #define f first #define s second #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define int ll #define sz(x) (ll)x.size() #define all(x) (x.begin(),x.end()) using namespace std; const ll INF = 1e12; const ll N =(5e5+5); // TODO : change value as per problem const ll MOD = 1e9+7; vector<pair<int,int>> adj[N]; set<pair<int,int>> adj2[N]; map<pll,ll> cost; void solve(){ int n,m; cin >> n >> m; for(int i =1;i<=m;i++){ int u,v; int ch; cin >> u >> v >> ch; adj2[u].in({ch,v}); adj2[v].in({ch,u}); cost[{u,v}] = ch; cost[{v,u}] = ch; } int ans = 0; for(int i =1 ;i<=n;i++){ int cur = 0; if((int)adj2[i].size() < 2) continue; auto it = --(adj2[i].end()); // it--; // auto it2 = it-1; pll p = *(it); int u = p.s; cur += p.f; it--; p = *(it); int v = p.s; cur += p.f; cur += cost[{u,v}]; ans = max(ans,cur); } for(int i =1;i<=n;i++){ int cur = 0; for(auto p:adj2[i]){ cur += p.f; } ans = max(ans,cur); } cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); // freopen(".in","r",stdin);freopen(".out","w",stdout); ll tt=1; // cin >> tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...