oj.uz

Submission #736416

# Submission time Handle Problem Language Result Execution time Memory
736416 2023-05-05T15:11:22 Z josanneo22 Cities (BOI16_cities) C++17
100 / 100
 999 ms 36028 KB 
#include <algorithm>
#include <queue>
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fst first
#define snd second
#define vpi vector<pii>
#define ppi pair<int, pii>
 
const int INF = 1e16;
 
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int s=0;
	char ch=getchar(),last;
	while(ch<'0'||ch>'9') last=ch,ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return last=='-'?-s:s;
}
int num[100];
inline void rt(int x)
{
	if(x<0) putchar('-'),x=-x;;
	int len=0;
	do num[len++]=x%10;while(x/=10);
	while(len--) putchar(num[len]+'0');
}
priority_queue<pii> pq;
int n, k, m, spc[6];
int dst[1 << 4][100001];
vpi adj[100001];
int res = INF; 
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	n=rd();k=rd();m=rd();
	for (int i = 0; i < k; i++) {spc[i]=rd(); spc[i]--;}
	k--;
	for (int i = 0; i < m; i++)
	{
		int u=rd(),v=rd(),w=rd();
		adj[u - 1].push_back({w, v - 1});
		adj[v - 1].push_back({w, u - 1});
	}
	for (int i = 0; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++) {dst[i][j] = INF;}
	}
	for (int i = 0; i < k; i++) {dst[1 << i][spc[i]] = 0;}
	for (int i = 1; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int s = i; s; s = (s - 1) & i)
			{
				dst[i][j] = min(dst[i][j], dst[s][j] + dst[i ^ s][j]);
			}
			pq.push({-dst[i][j], j});
		}
		while (pq.size())
		{
			int u = pq.top().snd; int d = -pq.top().fst; pq.pop();
			if (dst[i][u] == d)
			{
				for (auto v : adj[u])
				{
					if (dst[i][u] + v.fst < dst[i][v.snd])
					{
						dst[i][v.snd] = dst[i][u] + v.fst;
						pq.push({-dst[i][v.snd], v.snd});
					}
				}
			}
		}
	}
	rt(dst[(1 << k) - 1][spc[k]]);
	return 0;
}

Compilation message

cities.cpp: In function 'long long int rd()':
cities.cpp:22:18: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |  return last=='-'?-s:s;
      |         ~~~~~~~~~^~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 22416 KB Output is correct
2 Correct 232 ms 25676 KB Output is correct
3 Correct 176 ms 17432 KB Output is correct
4 Correct 22 ms 17228 KB Output is correct
5 Correct 128 ms 24992 KB Output is correct
6 Correct 24 ms 17144 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 5 ms 2976 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 25536 KB Output is correct
2 Correct 479 ms 28764 KB Output is correct
3 Correct 290 ms 20544 KB Output is correct
4 Correct 306 ms 24764 KB Output is correct
5 Correct 70 ms 19240 KB Output is correct
6 Correct 33 ms 19416 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 31716 KB Output is correct
2 Correct 999 ms 36028 KB Output is correct
3 Correct 993 ms 35120 KB Output is correct
4 Correct 682 ms 26696 KB Output is correct
5 Correct 512 ms 27848 KB Output is correct
6 Correct 120 ms 20012 KB Output is correct
7 Correct 35 ms 19780 KB Output is correct