Submission #736415

#	Time	Username	Problem	Language	Result	Execution time	Memory
736415		josanneo22	Cities (BOI16_cities)	C++17	0 / 100	978 ms	36020 KiB

cities

#include <algorithm>
#include <queue>
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll, int>
#define fst first
#define snd second
#define vpi vector<pii>
#define ppi pair<ll, pii>
 
const ll 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];
ll dst[1 << 4][100001];
vpi adj[100001];
ll res = INF; 
int 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; ll 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 (stderr)

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

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