Submission #25391

#	Time	Username	Problem	Language	Result	Execution time	Memory
25391		tuna_salad	Cities (BOI16_cities)	C++14	100 / 100	2663 ms	41924 KiB

cities

//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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26