oj.uz

답안 #544945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544945 2022-04-03T07:54:43 Z MilosMilutinovic Cities (BOI16_cities) C++14
37 / 100
 6000 ms 39648 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);
	priority_queue<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.push(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.push(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()){
		ll d=que.top().first;
		int u=que.top().second.first;
		int mask=que.top().second.second;
		que.pop();
		if(dist[u][mask]<d)continue;
		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){
					dist[v][ns]=dist[u][mask]+dist[v][s]+w;
					que.push(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

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

Subtask #2
0 / 14.0

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

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1723 ms 28272 KB Output is correct
2 Correct 286 ms 28216 KB Output is correct
3 Correct 110 ms 28144 KB Output is correct
4 Correct 682 ms 28216 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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