제출 #1122616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122616		ardadut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	0 / 100	472 ms	62672 KiB

pigus_skrydziai

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/


ll n,m,ans = 0;
vector<ll> profit;
vector<vector<pair<ll,ll>>> adj;
vector<bool> vis;
map<pair<ll,ll>,ll> mapp;

inline bool comp(pair<ll,ll> pair1, pair<ll,ll> pair2){
    return pair1.second > pair2.second;
}

inline void dfs(ll node, ll parent, ll edge){

    vis[node] = 1;

    for(auto go : adj[node]){
        if(go.first == parent) continue;
        if(mapp[{go.first,parent}] > 0){
            ans = max(ans,go.second + edge + mapp[{go.first,parent}]);
        }
        if(!vis[go.first]) dfs(go.first,node,go.second);
    }

}

inline void solve(){

    cin >> n >> m;
    adj.resize(n+1);
    vis.resize(n+1,0);
    profit.resize(n+1,0);

    while(m--){
        ll a,b,c;
        cin >> a >> b >> c;
        profit[a] += c;
        profit[b] += c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
        mapp[{a,b}] = c;
        mapp[{b,a}] = c;
    }

    for(ll i = 1 ; i <= n ; i++){
        ans = max(ans,profit[i]);
        sort(adj[i].begin(), adj[i].end(), comp);
    }

    dfs(1,-1,0);

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 25
• Subtask 3: 0 / 16
• Subtask 4: 0 / 47