oj.uz

Submission #56877

# Submission time Handle Problem Language Result Execution time Memory
56877 2018-07-13T02:15:26 Z MatheusLealV Cities (BOI16_cities) C++17
74 / 100
 6000 ms 42812 KB 
#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();
	}
}

bool solved[6][6][6];
 
void solve2(int a, int b, int c, int d, int e)
{
	if(!solved[a][b][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]);

	if(!solved[a][b][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();
		}
	}

	solved[a][b][e] = true;
}
 
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

cities.cpp: In function 'int32_t main()':
cities.cpp:254:10: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     solve(a, b, c, d);
     ~~~~~^~~~~~~~~~~~
cities.cpp:254:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
cities.cpp:230:12: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
      solve2(a, b, c, d, e);
      ~~~~~~^~~~~~~~~~~~~~~
cities.cpp:225: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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 8 ms 5092 KB Output is correct
3 Correct 7 ms 5128 KB Output is correct
4 Correct 8 ms 5204 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 25236 KB Output is correct
2 Correct 374 ms 28084 KB Output is correct
3 Correct 162 ms 28084 KB Output is correct
4 Correct 108 ms 28084 KB Output is correct
5 Correct 364 ms 28084 KB Output is correct
6 Correct 132 ms 28084 KB Output is correct
7 Correct 11 ms 28084 KB Output is correct
8 Correct 9 ms 28084 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28084 KB Output is correct
2 Correct 13 ms 28084 KB Output is correct
3 Correct 8 ms 28084 KB Output is correct
4 Correct 11 ms 28084 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1308 ms 41800 KB Output is correct
2 Correct 1206 ms 41800 KB Output is correct
3 Correct 861 ms 41800 KB Output is correct
4 Correct 646 ms 41800 KB Output is correct
5 Correct 223 ms 41800 KB Output is correct
6 Correct 131 ms 41800 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6091 ms 42812 KB Time limit exceeded
2 Halted 0 ms 0 KB -