10360 | 2024. 04. 01 03:11:56 | Vargus | Rácsháló gráf | cpp17 | Elfogadva 50/50 | 130ms | 4204 KiB |
#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;
struct adat
{
ll hossz = INT_MAX;
vector < pair <ll, ll> > sz;
};
vector <adat> x;
struct tav
{
ll hova, kolt;
};
priority_queue <tav> t;
bool operator < (const tav& a, const tav& b)
{
return a.kolt > b.kolt;
}
vector <ll> maxi;
ll n, m;
void dijkstra(ll kezd)
{
tav akt;
t.push({ kezd, 0 });
x[kezd].hossz = 0;
while (!t.empty())
{
akt = t.top();
t.pop();
for (auto& e : x[akt.hova].sz)
{
if (x[e.first].hossz > (e.second + akt.kolt))
{
x[e.first].hossz = e.second + akt.kolt;
t.push({ e.first, x[e.first].hossz });
}
}
}
ll maximum = INT_MIN;
for (ll i = 1; i <= n * m; ++i)
if (x[i].hossz > maximum)
maximum = x[i].hossz;
maxi.push_back(maximum);
}
int main()
{
ll k;
cin >> n >> m >> k;
x.resize(n * m + 1);
for (ll i = 1; i <= n * m; ++i)
{
if (i > m)
{
x[i].sz.push_back({ i - m, 1 });
x[i - m].sz.push_back({ i, 1 });
}
if (i % m == 0)
continue;
x[i].sz.push_back({ i + 1, 1 });
x[i + 1].sz.push_back({ i, 1 });
}
for (ll i = 1; i <= k; ++i)
{
ll a, b;
cin >> a >> b;
x[a].sz.push_back({ b, 1 });
x[b].sz.push_back({ a, 1 });
for (ll j = 1; j <= n * m; ++j)
{
dijkstra(j);
for (ll g = 1; g <= n * m; ++g)
{
x[g].hossz = INT_MAX;
}
}
ll nagy = INT_MIN;
for (auto& e : maxi)
if (nagy < e)
nagy = e;
maxi.clear();
cout << nagy << endl;
}
return 0;
}
/*
3 4 4
1 6
7 10
2 12
4 9
*/
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1872 KiB | |||
2 | Elfogadva | 0/0 | 128ms | 2232 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2540 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2420 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2520 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2732 KiB | |||
7 | Elfogadva | 2/2 | 8ms | 2976 KiB | |||
8 | Elfogadva | 2/2 | 8ms | 3064 KiB | |||
9 | Elfogadva | 2/2 | 8ms | 3176 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3280 KiB | |||
11 | Elfogadva | 2/2 | 8ms | 3352 KiB | |||
12 | Elfogadva | 2/2 | 27ms | 3452 KiB | |||
13 | Elfogadva | 3/3 | 59ms | 3544 KiB | |||
14 | Elfogadva | 3/3 | 9ms | 3672 KiB | |||
15 | Elfogadva | 3/3 | 57ms | 3764 KiB | |||
16 | Elfogadva | 3/3 | 8ms | 3760 KiB | |||
17 | Elfogadva | 3/3 | 48ms | 3684 KiB | |||
18 | Elfogadva | 3/3 | 18ms | 3900 KiB | |||
19 | Elfogadva | 3/3 | 3ms | 3900 KiB | |||
20 | Elfogadva | 3/3 | 4ms | 3892 KiB | |||
21 | Elfogadva | 3/3 | 21ms | 3904 KiB | |||
22 | Elfogadva | 3/3 | 130ms | 4204 KiB |