This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |