Submission #498732

#TimeUsernameProblemLanguageResultExecution timeMemory
498732aurimsCheap flights (LMIO18_pigus_skrydziai)C++14
0 / 100
164 ms262148 KiB
#include <bits/stdc++.h> #define debug cout << "alio\n"; #define pb push_back #define MAXN 5000 using namespace std; /* input 5 4 1 2 1 1 3 2 1 4 1 2 4 1 */ struct miestas { vector<int> kaimynai; vector<int> pelnas; }; vector<miestas> miestai; vector<bool> aplankyti; void dfs(int idx, int deep) { aplankyti[idx] = true; if(deep <= 0) return; for(int sidx : miestai[idx].kaimynai) { if(aplankyti[sidx]) continue; cout << "deep: " << deep << '\n'; cout << idx << " kaimynas " << sidx << '\n'; cout << '\n'; dfs(sidx, --deep); } } int main() { //int m1[MAXN][MAXN]; int N, M; cin >> N >> M; /* for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { m1[i][j] = -1; } } */ miestai.resize(N); aplankyti.resize(N); for(int i = 0; i < N; i++) { miestai[i].pelnas.resize(N); for(int j = 0; j < N; j++) { miestai[i].pelnas[j] = -1; } } for(int i = 0; i < N; i++) aplankyti[i] = false; for(int i = 0; i < M; i++) { int a, b, p; cin >> a >> b >> p; miestai[a-1].kaimynai.pb(b-1); miestai[b-1].kaimynai.pb(a-1); miestai[a-1].pelnas[b-1] = p; miestai[b-1].pelnas[a-1] = p; /* m1[a-1][b-1] = p; m1[b-1][a-1] = p; */ } int mx = -1; // perrenkam visas zvaigzdes for(int i = 0; i < N; i++) { int sum = 0; for(int sidx : miestai[i].kaimynai) { sum += miestai[i].pelnas[sidx]; } if(sum > mx) mx = sum; } // perrenkam visus trikampius for(int i = 0; i < N; i++) { int sum = 0; int mxind_1 = 0; int mxind_2 = 0; for(int sidx : miestai[i].kaimynai) { if(miestai[i].pelnas[sidx] > miestai[i].pelnas[mxind_1]) { mxind_1 = sidx; } else if(miestai[i].pelnas[sidx] > miestai[i].pelnas[mxind_2]) { mxind_2 = sidx; } } if(miestai[mxind_1].pelnas[mxind_2] != -1) sum += miestai[mxind_1].pelnas[mxind_2] + miestai[i].pelnas[mxind_1] + miestai[i].pelnas[mxind_2]; if(sum > mx) mx = sum; } cout << mx << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...