oj.uz

Submission #1075485

# Submission time Handle Problem Language Result Execution time Memory
1075485 2024-08-26T06:58:44 Z kustizus Cities (BOI16_cities) C++17
100 / 100
 1482 ms 48856 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 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 29928 KB Output is correct
2 Correct 384 ms 29432 KB Output is correct
3 Correct 214 ms 20024 KB Output is correct
4 Correct 45 ms 15368 KB Output is correct
5 Correct 205 ms 26648 KB Output is correct
6 Correct 43 ms 15368 KB Output is correct
7 Correct 4 ms 2904 KB Output is correct
8 Correct 3 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 2904 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 36224 KB Output is correct
2 Correct 725 ms 35696 KB Output is correct
3 Correct 477 ms 26308 KB Output is correct
4 Correct 404 ms 27288 KB Output is correct
5 Correct 116 ms 17844 KB Output is correct
6 Correct 46 ms 17744 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1470 ms 48856 KB Output is correct
2 Correct 1482 ms 48804 KB Output is correct
3 Correct 1389 ms 48228 KB Output is correct
4 Correct 903 ms 38856 KB Output is correct
5 Correct 737 ms 33592 KB Output is correct
6 Correct 212 ms 19212 KB Output is correct
7 Correct 54 ms 17744 KB Output is correct