Submission #544939

#	Time	Username	Problem	Language	Result	Execution time	Memory
544939		MilosMilutinovic	Cities (BOI16_cities)	C++14	51 / 100	6069 ms	177212 KiB

cities

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x>y?x=y,1:0;}

int n,k,m,id[100005];
ll dist[100005][1<<5];
vector<pii> g[100005];
vector<int> gas[1<<5];

int main(){
	scanf("%d%d%d",&n,&k,&m);
	memset(id,-1,sizeof id);
	memset(dist,-1,sizeof dist);
	set<pair<ll,pii>> que;
	for(int i=1;i<=k;i++){
		int x;scanf("%d",&x);
		id[x]=i-1;
		dist[x][1<<(i-1)]=0;
		que.insert(mp(0,mp(x,1<<(i-1))));
	}
	for(int s=0;s<(1<<k);s++)for(int t=0;t<(1<<k);t++)if(!(s&t))gas[s].pb(t);
	for(int i=1;i<=n;i++)dist[i][0]=0,que.insert(mp(0,mp(i,0)));
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		g[u].pb(mp(v,w)); g[v].pb(mp(u,w));
	}
	while(!que.empty()){
		auto it=que.begin();
		int u=it->second.first;
		int mask=it->second.second;
		que.erase(it);
		for(auto e:g[u]){
			int v=e.first,w=e.second;
			//int nmask=(mask|(id[v]==-1?0:(1<<id[v])));
			for(int s:gas[mask]){
				if(dist[v][s]==-1)continue;
				int ns=(s|mask);
				if(dist[v][ns]==-1||dist[v][ns]>dist[u][mask]+dist[v][s]+w){
					if(dist[v][ns]!=-1)que.erase(que.find(mp(dist[v][ns],mp(v,ns))));
					dist[v][ns]=dist[u][mask]+dist[v][s]+w;
					que.insert(mp(dist[v][ns],mp(v,ns)));
				}
			}
		}
	}
	ll ans=(ll)1e18;
	for(int i=1;i<=n;i++)ans=min(ans,dist[i][(1<<k)-1]);
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d%d",&n,&k,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   int x;scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
cities.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   int u,v,w;scanf("%d%d%d",&u,&v,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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