oj.uz

Submission #25391

# Submission time Handle Problem Language Result Execution time Memory
25391 2017-06-21T21:35:32 Z tuna_salad Cities (BOI16_cities) C++14
100 / 100
 2663 ms 41924 KB 
//spnauT
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int _=b,i=a;i<_;++i)
#define ROF(i,b,a) for(int _=a,i=b;i>_;--i)
#define REP(n) for(int _=(n);_--;)
#define _1 first
#define _2 second
#define PB push_back
#define SZ(x) int((x).size())
#define ALL(x) begin(x),end(x)
#define MSET(m,v) memset(m,v,sizeof(m))
#define MAX_PQ(T) priority_queue<T>
#define MIN_PQ(T) priority_queue<T,vector<T>,greater<T>>
#define IO {ios_base::sync_with_stdio(0);cin.tie(0);}
#define nl '\n'
#define cint1(a) int a;cin>>a
#define cint2(a,b) int a,b;cin>>a>>b
#define cint3(a,b,c) int a,b,c;cin>>a>>b>>c
using namespace std;using LL=int64_t;using PII=pair<int,int>;
using VI=vector<int>;using VL=vector<LL>;using VP=vector<PII>;
template<class A,class B>bool mina(A&x,B&&y){return y<x?(x=forward<B>(y),1):0;}
template<class A,class B>bool maxa(A&x,B&&y){return x<y?(x=forward<B>(y),1):0;}

const int MAX_N {100004};
const int MAX_M {200004};
const int MAX_K {5};
const int MAX_2_K {1 << 5};
const int MASK_K {MAX_2_K - 1};
const LL infLL {1LL << 50};

VP E[MAX_N];

LL dist[MAX_2_K][MAX_N];

int main()
{
	IO;
	cint3(N,K,M);
	VI I;
	REP(K)
	{
		cint1(a);
		--a;
		I.PB(a);
	}
	REP(M)
	{
		cint3(a,b,c);
		--a; --b;
		E[a].PB({b,c});
		E[b].PB({a,c});
	}

	using P2 = pair<LL,int>;

	MIN_PQ(P2) Q;

	const int bit_goal {(1 << K) - 1};
	fill(dist[0], dist[MAX_2_K], infLL);
	auto dist0 = dist[0];
	FOR(i,0,N) dist0[i] = 0;
	FOR(j,0,K) dist[1 << j][I[j]] = 0;

	FOR(mask,1,1<<K)
	{
		auto dist_mask = dist[mask];
		FOR(a,1,mask) if((a & mask) == a)
		{
			int b {a ^ mask};
			auto dist_a = dist[a];
			auto dist_b = dist[b];
			FOR(i,0,N) mina(dist_mask[i], dist_a[i] + dist_b[i]);
		}

		FOR(i,0,N) if(dist_mask[i] < infLL) Q.emplace(dist_mask[i], i);
		auto f = [&](LL d, int u)
		{
			if(mina(dist_mask[u],d)) Q.push({d,u});
		};

		while(!Q.empty())
		{
			LL d;
			int u;
			tie(d,u) = Q.top();
			Q.pop();
			if(dist_mask[u] < d) continue;
			for(PII e: E[u]) f(d + e._2, e._1);
		}
	}

	LL sol {infLL};
	auto dist_full = dist[bit_goal];
	FOR(i,0,N) mina(sol, dist_full[i]);
	cout << sol << nl;

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29528 KB Output is correct
2 Correct 0 ms 29528 KB Output is correct
3 Correct 3 ms 29528 KB Output is correct
4 Correct 3 ms 29528 KB Output is correct
5 Correct 0 ms 29528 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 41924 KB Output is correct
2 Correct 679 ms 41868 KB Output is correct
3 Correct 403 ms 35764 KB Output is correct
4 Correct 76 ms 34048 KB Output is correct
5 Correct 363 ms 41920 KB Output is correct
6 Correct 83 ms 34044 KB Output is correct
7 Correct 9 ms 29660 KB Output is correct
8 Correct 6 ms 29660 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29660 KB Output is correct
2 Correct 9 ms 29684 KB Output is correct
3 Correct 9 ms 29528 KB Output is correct
4 Correct 3 ms 29660 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 41920 KB Output is correct
2 Correct 1373 ms 41724 KB Output is correct
3 Correct 889 ms 35764 KB Output is correct
4 Correct 753 ms 38372 KB Output is correct
5 Correct 213 ms 35512 KB Output is correct
6 Correct 96 ms 35736 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2663 ms 41916 KB Output is correct
2 Correct 2606 ms 41916 KB Output is correct
3 Correct 2389 ms 41772 KB Output is correct
4 Correct 1776 ms 35768 KB Output is correct
5 Correct 1353 ms 38364 KB Output is correct
6 Correct 316 ms 35508 KB Output is correct
7 Correct 109 ms 35712 KB Output is correct