oj.uz

답안 #544934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544934 2022-04-03T07:37:23 Z MilosMilutinovic Cities (BOI16_cities) C++14
51 / 100
 6000 ms 174692 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];

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 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=0;s<(1<<k);s++){
				if(dist[v][s]==-1)continue;
				int ns=(s|nmask);
				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:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d%d",&n,&k,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   int x;scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
cities.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   int u,v,w;scanf("%d%d%d",&u,&v,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 27988 KB Output is correct
2 Correct 13 ms 28024 KB Output is correct
3 Correct 13 ms 28020 KB Output is correct
4 Correct 12 ms 28004 KB Output is correct
5 Correct 14 ms 28120 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2904 ms 64808 KB Output is correct
2 Correct 2231 ms 60484 KB Output is correct
3 Correct 506 ms 39668 KB Output is correct
4 Correct 159 ms 36064 KB Output is correct
5 Correct 786 ms 47044 KB Output is correct
6 Correct 99 ms 35924 KB Output is correct
7 Correct 18 ms 28424 KB Output is correct
8 Correct 15 ms 28192 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 28852 KB Output is correct
2 Correct 27 ms 28628 KB Output is correct
3 Correct 21 ms 28368 KB Output is correct
4 Correct 26 ms 28496 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6049 ms 107264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6093 ms 174692 KB Time limit exceeded
2 Halted 0 ms 0 KB -