제출 #1143088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143088		ionutza	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	1407 ms	99328 KiB

pigus_skrydziai

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#define ULL unsigned long long

using namespace std;

int nodes, edges;
ULL costs[300003], ans;
vector <int> graph[300005];
map <pair <int, int>, ULL> frecv;
bool viz[300005];

void dfs (int current, int previous){
    viz[current] = true;
    for (auto future:graph[current]){
        if (viz[future] == false){
            dfs(future, current);
        }
        else if (viz[future] == true && frecv.find({future, previous}) != frecv.end()){
            ans = max(ans, frecv[{previous, current}] + frecv[{current, future}] + frecv[{previous, future}]);
        }
    }
}

int main (){
    int x, y, cost;

    cin >> nodes >> edges;

    /// exista doua sub grafuri pe care le pot luat pentru a ajunge la ce vreau
    /// o stea, sau un subgraf care e complet
    for (int i=1; i<=edges; ++i){
        cin >> x >> y >> cost;

        costs[x] += cost;
        costs[y] += cost;
        graph[x].push_back(y);
        graph[y].push_back(x);
        frecv[{x, y}] = cost;
        frecv[{y, x}] = cost;
    }

    for (int i=1; i<=nodes; ++i){
        ans = max(ans, costs[i]);
    }
    for (int i=1; i<=nodes; ++i){
        if (viz[i] == false)
            dfs(i, 0);
    }
    cout << ans;
    
    return 0;
}

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