Submission #56870

#	Time	Username	Problem	Language	Result	Execution time	Memory
56870		MatheusLealV	Cities (BOI16_cities)	C++17	74 / 100	6058 ms	76312 KiB

cities

#include <bits/stdc++.h>
#define N 200050
#define int long long
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll inf = 200000000000000000LL, dist[N][10], dis[N], dis2[N];

ll ans = inf;

int n, m, k, C[N], id[N];

vector<pii> grafo[N];

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())
	{
		int 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});
			}
		}
	}
}

ll dijkstra2()
{
	for(int i = 0; i <= n + 1; i++) dis[i] = inf;

	dis[0] = 0;

	priority_queue < pii, vector< pii >, greater < pii > > pq;

	pq.push({0, 0});

	while(!pq.empty())
	{
		int x = pq.top().s, d = pq.top().f;

		pq.pop();

		if(d > dis[x]) continue;

		for(auto v: grafo[x])
		{
			if(dis[v.f] > dis[x] + v.s)
			{
				dis[v.f] = dis[x] + v.s;

				pq.push({dis[v.f], v.f});
			}
		}
	}

	return dis[n + 1];
}

ll dijkstra3()
{
	for(int i = 0; i <= n + 1; i++) dis2[i] = inf;

	dis2[n + 1] = 0;

	priority_queue < pii, vector< pii >, greater < pii > > pq;

	pq.push({0, n + 1});

	while(!pq.empty())
	{
		int x = pq.top().s, d = pq.top().f;

		pq.pop();

		if(d > dis2[x]) continue;

		for(auto v: grafo[x])
		{
			if(dis2[v.f] > dis2[x] + v.s)
			{
				dis2[v.f] = dis2[x] + v.s;

				pq.push({dis2[v.f], v.f});
			}
		}
	}

	return dis2[0];
}

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());

	for(int i = 1; i <= n; i++)
	{
		grafo[i].pop_back();

		grafo[i].pop_back();

		grafo[0].pop_back();

		grafo[n + 1].pop_back();
	}
}

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(); dijkstra3();

	for(int i = 1; i <= n; i++) ans = min(ans, dis[i] + dis2[i] + 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:244:10: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     solve(a, b, c, d);
     ~~~~~^~~~~~~~~~~~
cities.cpp:244:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
cities.cpp:220:12: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
      solve2(a, b, c, d, e);
      ~~~~~~^~~~~~~~~~~~~~~
cities.cpp:215: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: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26