oj.uz

Submission #391128

# Submission time Handle Problem Language Result Execution time Memory
391128 2021-04-18T04:47:02 Z AriaH Cities (BOI16_cities) C++11
100 / 100
 2561 ms 48996 KB 
/** 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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7628 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 7 ms 11596 KB Output is correct
4 Correct 11 ms 18664 KB Output is correct
5 Correct 19 ms 31984 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 28756 KB Output is correct
2 Correct 674 ms 28092 KB Output is correct
3 Correct 436 ms 20812 KB Output is correct
4 Correct 98 ms 20880 KB Output is correct
5 Correct 409 ms 23624 KB Output is correct
6 Correct 81 ms 16968 KB Output is correct
7 Correct 10 ms 11800 KB Output is correct
8 Correct 7 ms 7884 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18764 KB Output is correct
2 Correct 15 ms 18788 KB Output is correct
3 Correct 14 ms 18768 KB Output is correct
4 Correct 14 ms 18836 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1298 ms 35540 KB Output is correct
2 Correct 1267 ms 35068 KB Output is correct
3 Correct 869 ms 27808 KB Output is correct
4 Correct 688 ms 32772 KB Output is correct
5 Correct 215 ms 28660 KB Output is correct
6 Correct 102 ms 30416 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2561 ms 48784 KB Output is correct
2 Correct 2500 ms 48996 KB Output is correct
3 Correct 2475 ms 48360 KB Output is correct
4 Correct 1713 ms 41192 KB Output is correct
5 Correct 1307 ms 46188 KB Output is correct
6 Correct 323 ms 42088 KB Output is correct
7 Correct 123 ms 43424 KB Output is correct