Submission #56874

#	Time	Username	Problem	Language	Result	Execution time	Memory
56874		MatheusLealV	Cities (BOI16_cities)	C++17	52 / 100	6090 ms	95904 KiB

cities

#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
 
ll inf = 200000000000000000LL, dist[N][10], dis[N][6][6], dis2[N][6][6];
 
ll ans = inf;
 
int n, m, k, C[N], id[N];
 
vector<pii> grafo[N];
 
inline void dijkstra(int ini)
{
	int q = id[ini];
 
	priority_queue< pii, vector< pii >, greater <pii> > pq;
 
	for(int i = 1; i <= n; i++) dist[i][q] = inf;
 
	dist[ini][q] = 0;
 
	pq.push({0, ini});
 
	while(!pq.empty())
	{
		ll x = pq.top().s, d = pq.top().f;
 
		//cout<<x<<" "<<q<<" "<<dist[x][q]<<"\n";
 
		pq.pop();
 
		if(d > dist[x][q]) continue;
 
		for(auto v: grafo[x])
		{
			//cout<<"oi "<<v.f<<" "<<dist[v.f][q]<<" "<<dist[x][q] + v.s<<"\n";
			if(dist[v.f][q] > dist[x][q] + v.s)
			{
				dist[v.f][q] = dist[x][q] + v.s;
 
				pq.push({dist[v.f][q], v.f});
			}
		}
	}
}

bool calc[6][6], calc2[6][6];
 
inline ll dijkstra2(int a, int b)
{
	if(calc2[a][b]) return dis[n + 1][a][b];

	calc2[a][b] = true;

	for(int i = 0; i <= n + 1; i++) dis[i][a][b] = inf;
 
	dis[0][a][b] = 0;
 
	priority_queue < pii, vector< pii >, greater < pii > > pq;
 
	pq.push({0, 0});
 
	while(!pq.empty())
	{
		ll x = pq.top().s, d = pq.top().f;
 
		pq.pop();
 
		if(d > dis[x][a][b]) continue;
 
		for(auto v: grafo[x])
		{
			if(dis[v.f][a][b] > dis[x][a][b] + v.s)
			{
				dis[v.f][a][b] = dis[x][a][b] + v.s;
 
				pq.push({dis[v.f][a][b], v.f});
			}
		}
	}
 
	return dis[n + 1][a][b];
}
 
inline void dijkstra3(int a, int b)
{
	if(calc[a][b]) return;

	calc[a][b] = true;

	for(int i = 0; i <= n + 1; i++) dis2[i][a][b] = inf;
 
	dis2[n + 1][a][b] = 0;
 
	priority_queue < pii, vector< pii >, greater < pii > > pq;
 
	pq.push({0, n + 1});
 
	while(!pq.empty())
	{
		ll x = pq.top().s, d = pq.top().f;
 
		pq.pop();
 
		if(d > dis2[x][a][b]) continue;
 
		for(auto v: grafo[x])
		{
			if(dis2[v.f][a][b] > dis2[x][a][b] + v.s)
			{
				dis2[v.f][a][b] = dis2[x][a][b] + v.s;
 
				pq.push({dis2[v.f][a][b], v.f});
			}
		}
	}
 }
 
inline void solve(int a, int b, int c, int d)
{
	for(int i = 1; i <= n; i++)
	{
		ll A = dist[i][a] + dist[i][b], B = dist[i][c] + dist[i][d];
 
		grafo[0].push_back({i, A});
 
		grafo[i].push_back({0, A});
 
		grafo[n + 1].push_back({i, B});
 
		grafo[i].push_back({n + 1, B});
	}
 
	ans = min(ans, dijkstra2(a, b));
 
	for(int i = 1; i <= n; i++)
	{
		grafo[i].pop_back();
 
		grafo[i].pop_back();
 
		grafo[0].pop_back();
 
		grafo[n + 1].pop_back();
	}
}
 
inline void solve2(int a, int b, int c, int d, int e)
{
	for(int i = 1; i <= n; i++)
	{
		ll A = dist[i][a] + dist[i][b], B = dist[i][c] + dist[i][d];
 
		grafo[0].push_back({i, A});
 
		grafo[i].push_back({0, A});
 
		grafo[n + 1].push_back({i, B});
 
		grafo[i].push_back({n + 1, B});
	}
 
	dijkstra2(a, b); dijkstra3(a, b);
 
	for(int i = 1; i <= n; i++) ans = min(ans, dis[i][a][b] + dis2[i][a][b] + dist[i][e]);
 
	for(int i = 1; i <= n; i++)
	{
		grafo[i].pop_back();
 
		grafo[i].pop_back();
 
		grafo[0].pop_back();
 
		grafo[n + 1].pop_back();
	}
}
 
int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>k>>m;
 
	for(int i = 1; i <= k; i++) cin>>C[i], id[C[i]] = i;
 
	for(int i = 1, a, b, c; i <= m; i++)
	{
		cin>>a>>b>>c;
 
		grafo[a].push_back({b, c});
 
		grafo[b].push_back({a, c});
	}
 
	for(int i = 1; i <= k; i++) dijkstra(C[i]);
 
	if(k == 5)
	{
		for(int a = 1; a <= k; a++)
		{
			for(int b = a + 1; b <= k; b++)
			{
				for(int e = 1; e <= k; e++)
				{
					if(e == a or e == b) continue;
 
					int c, d;
 
					if(a != 1 and b != 1 and e != 1) c = 1;
					if(a != 2 and b != 2 and e != 2) c = 2;
					if(a != 3 and b != 3 and e != 3) c = 3;
					if(a != 4 and b != 4 and e != 4) c = 4;
					if(a != 5 and b != 5 and e != 5) c = 5;
 
					if(a != 1 and b != 1 and c != 1 and e != 1) d = 1;
					if(a != 2 and b != 2 and c != 2 and e != 2) d = 2;
					if(a != 3 and b != 3 and c != 3 and e != 3) d = 3;
					if(a != 4 and b != 4 and c != 4 and e != 4) d = 4;
					if(a != 5 and b != 5 and c != 5 and e != 5) d = 5;
 
					solve2(a, b, c, d, e);
				}
			}
		}
	}
 
	else if(k == 4)
	{
		for(int a = 1; a <= k; a++)
		{
			for(int b = a + 1; b <= k; b++)
			{
				int c, d;
 
				if(a != 1 and b != 1) c = 1;
				if(a != 2 and b != 2) c = 2;
				if(a != 3 and b != 3) c = 3;
				if(a != 4 and b != 4) c = 4;
 
				if(a != 1 and b != 1 and c != 1) d = 1;
				if(a != 2 and b != 2 and c != 2) d = 2;
				if(a != 3 and b != 3 and c != 3) d = 3;
				if(a != 4 and b != 4 and c != 4) d = 4;
 
				solve(a, b, c, d);
			}
		}
	}
 
	else
	{
		if(k == 3)
 
		for(int i = 1; i <= n; i++) ans = min(ans, dist[i][1] + dist[i][2] + dist[i][3]);
 
		else if(k == 2) ans = dist[C[1]][2];
	}
 
	cout<<ans<<"\n";
}

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:239:12: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int c, d;
            ^
cities.cpp:239:9: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int c, d;
         ^
cities.cpp:213:13: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
      int c, d;
             ^
cities.cpp:222:33: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if(a != 2 and b != 2 and c != 2 and e != 2) d = 2;
                               ~~^~~~

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26