Submission #391128

#	Time	Username	Problem	Language	Result	Execution time	Memory
391128		AriaH	Cities (BOI16_cities)	C++11	100 / 100	2561 ms	48996 KiB

cities

/** I can do this all day **/

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 1e18;
const int LOG = 22;
const int M = 5;

int n, k, m, imp[M], mark[N];

ll dis[M][N], dp[1 << M][N], cu[N];

vector < pll > G[N];

void dij(int id)
{
	memset(mark, 0, sizeof mark);
	int V = imp[id];
	for(int i = 0; i < N; i ++)
	{
		dis[id][i] = inf;
	}
	dis[id][V] = 0;
	priority_queue < pll, vector < pll >, greater < pll > > st;
	st.push(Mp(0, V));
	while(SZ(st))
	{
		int v = st.top().S;
		st.pop();
		if(mark[v]) continue;
		mark[v] = 1;
		for(auto y : G[v])
		{
			ll u = y.F, cost = y.S;
			if(dis[id][u] > dis[id][v] + cost)
			{
				dis[id][u] = dis[id][v] + cost;
				st.push(Mp(dis[id][u], u));
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &k, &m);
	for(int i = 0; i < k ;i ++)
	{
		scanf("%d", &imp[i]);
	}
	for(int i = 1; i <= m; i ++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(Mp(b, c));
		G[b].push_back(Mp(a, c));
	}
	for(int i = 0; i < k; i ++)
	{
		dij(i);
	}
	ll tot = inf;
	for(int mask = 1; mask < 1 << k; mask ++)
	{
		memset(mark, 0, sizeof mark);
		for(int i = 0; i < N; i ++) cu[i] = inf;
		priority_queue < pll, vector < pll >, greater < pll > > st;
		for(int i = 1; i <= n; i ++)
		{
			for(int j = 0; j < k; j ++)
			{
				if(mask >> j & 1)
				{
					cu[i] = min(cu[i], dp[mask ^ 1 << j][i] + dis[j][i]);
				}
			}
			st.push(Mp(cu[i], i));
		}
		while(SZ(st))
		{
			int v = st.top().S;
			st.pop();
			if(mark[v]) continue;
			mark[v] = 1;
			for(auto y : G[v])
			{
				ll u = y.F, cost = y.S;
				if(cu[u] > cu[v] + cost)
				{
					cu[u] = cu[v] + cost;
					st.push(Mp(cu[u], u));
				}
			}
		}
		if(mask == (1 << k) - 1)
		{
			for(int i = 1; i <= n; i ++)
			{
				tot = min(tot, cu[i]);
			}
		}
		memcpy(dp[mask], cu, sizeof cu);
	}
	printf("%lld", tot);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d%d%d", &n, &k, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", &imp[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
cities.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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