Submission #1075485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075485		kustizus	Cities (BOI16_cities)	C++17	100 / 100	1482 ms	48856 KiB

cities

// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e5;
int n,k,m,d[10],dis[N+5],dp[35][N+5];
vector <pair<int,int>> g[N+5];
void Dij(int x){
	int o=d[__lg(x)+1];
	for (int i=1;i<=n;++i) dis[i]=1e18;
	priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	dis[o]=0;
	pq.push({dis[o],o});
	while (!pq.empty()){
		pair <int,int> pos=pq.top();
		pq.pop();
		if (dis[pos.second]!=pos.first) continue;
		for (pair <int,int> j : g[pos.second])
			if (dis[j.first]>pos.first+j.second){
				dis[j.first]=pos.first+j.second;
				pq.push({dis[j.first],j.first});
			}
	}
	for (int i=1;i<=n;++i) dp[x][i]=dis[i];
}
void Solve(){
	cin>>n>>k>>m;
	for (int i=1;i<=k;++i) cin>>d[i];
	for (int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	int mask=(1<<k);
	for (int i=1;i<mask;++i)
		for (int j=1;j<=n;++j)
			dp[i][j]=1e18;
	for (int i=1;i<mask;++i){
		bool ok=true;
		for (int j=i&(i-1);j;j=(j-1)&i)
			for (int k=1;k<=n;++k){
				ok=false;
				dp[i][k]=min(dp[i][k],dp[j][k]+dp[i^j][k]);
			}
		if (ok) Dij(i);
		priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
		for (int j=1;j<=n;++j) pq.push({dp[i][j],j});
		while (!pq.empty()){
			pair <int,int> p=pq.top();
			pq.pop();
			if (p.first!=dp[i][p.second]) continue;
			for (pair <int,int> j : g[p.second])
				if (dp[i][j.first]>p.first+j.second){
					dp[i][j.first]=p.first+j.second;
					pq.push({dp[i][j.first],j.first});
				}
		}
	}
	int ans=1e18;
	for (int i=1;i<=n;++i) ans=min(ans,dp[(1<<k)-1][i]);
	cout<<ans;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if (fopen("in.inp","r")){
		freopen ("in.inp","r",stdin);
		freopen ("ou.out","w",stdout);
	}
	int t=1;
	// cin>>t;
	while (t--) Solve();
	cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC <<"ms.";
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:69:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   freopen ("in.inp","r",stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
cities.cpp:70:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   freopen ("ou.out","w",stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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