oj.uz

Submission #1075486

# Submission time Handle Problem Language Result Execution time Memory
1075486 2024-08-26T06:59:07 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1515 ms 44580 KB 
// #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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 25752 KB Output is correct
2 Correct 353 ms 25168 KB Output is correct
3 Correct 212 ms 17932 KB Output is correct
4 Correct 40 ms 11856 KB Output is correct
5 Correct 203 ms 22296 KB Output is correct
6 Correct 38 ms 11860 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3160 KB Output is correct
2 Correct 5 ms 3164 KB Output is correct
3 Correct 4 ms 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 32088 KB Output is correct
2 Correct 742 ms 31684 KB Output is correct
3 Correct 463 ms 24212 KB Output is correct
4 Correct 392 ms 23176 KB Output is correct
5 Correct 122 ms 14120 KB Output is correct
6 Correct 48 ms 14416 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1438 ms 44484 KB Output is correct
2 Correct 1515 ms 44580 KB Output is correct
3 Correct 1444 ms 43988 KB Output is correct
4 Correct 964 ms 36728 KB Output is correct
5 Correct 782 ms 29488 KB Output is correct
6 Correct 181 ms 15352 KB Output is correct
7 Correct 57 ms 14420 KB Output is correct