Submission #25387

#	Time	Username	Problem	Language	Result	Execution time	Memory
25387		tuna_salad	Cities (BOI16_cities)	C++14	74 / 100	4000 ms	232384 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];
VP B[MAX_2_K];

LL dist[MAX_N << MAX_K];

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

	FOR(a,0,1<<K) FOR(b,0,1<<K) if(not (a & b)) B[a].PB({b,a|b});

	fill(ALL(dist), infLL);
	using P2 = pair<LL,int>;

	MIN_PQ(P2) Q;
	auto f = [&](LL d, int u, int b)
	{
		int s {(u << MAX_K) | b};
		if(mina(dist[s],d)) Q.push({d,s});
	};
	FOR(i,0,N) dist[i << MAX_K] = 0;
	FOR(j,0,K) f(0, I[j], 1<<j);

	const int bit_goal {(1 << K) - 1};
	while(!Q.empty())
	{
		LL d;
		int s;
		tie(d,s) = Q.top();
		Q.pop();
		if(dist[s] < d) continue;

		int u {s >> MAX_K};
		int b {s & MASK_K};

		if(b == bit_goal)
		{
			cout << d << nl;
			break;
		}

		int s1 {u << MAX_K};
		for(PII eb: B[b])
		{
			LL d1 {d + dist[s1 ^ eb._1]};
			if(d1 < infLL) f(d1, u, eb._2);
		}

		for(PII e: E[u])
		{
			int v {e._1};
			LL d1 {d + e._2};
			int s2 {v << MAX_K};
			for(PII eb: B[b])
			{
				LL d2 {d1 + dist[s2 ^ eb._1]};
				if(d2 < infLL) f(d2, v, eb._2);
			}
		}
	}

	return 0;
}

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