oj.uz

Submission #544939

# Submission time Handle Problem Language Result Execution time Memory
544939 2022-04-03T07:45:44 Z MilosMilutinovic Cities (BOI16_cities) C++14
51 / 100
 6000 ms 177212 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28032 KB Output is correct
2 Correct 11 ms 28048 KB Output is correct
3 Correct 14 ms 27988 KB Output is correct
4 Correct 12 ms 27988 KB Output is correct
5 Correct 14 ms 28000 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2691 ms 60708 KB Output is correct
2 Correct 2293 ms 56356 KB Output is correct
3 Correct 536 ms 37648 KB Output is correct
4 Correct 124 ms 32716 KB Output is correct
5 Correct 668 ms 43024 KB Output is correct
6 Correct 93 ms 32844 KB Output is correct
7 Correct 17 ms 28416 KB Output is correct
8 Correct 14 ms 28280 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28820 KB Output is correct
2 Correct 27 ms 28608 KB Output is correct
3 Correct 18 ms 28244 KB Output is correct
4 Correct 23 ms 28404 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6069 ms 103132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6063 ms 177212 KB Time limit exceeded
2 Halted 0 ms 0 KB -