제출 #712525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712525		yuseok0803	Museum (CEOI17_museum)	C++14	100 / 100	473 ms	746232 KiB

museum

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>  
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;

int n,need,x;
v(pii) pushvec;
v(v(pii)) vec;
int cnt[100010];
int dp[10010][10010][2];
//dp[start][visited rooms cnt][start==end?]

void find(int now, int parent){
	dp[now][1][0]=0;
	dp[now][1][1]=0;
	fi(2, need+1) dp[now][i][0] = dp[now][i][1] = 999999999;
	
	cnt[now]=1;
	int sz = vec[now].size();
	fi(0,sz){
		pii next = vec[now][i];
		if(next.first == parent) continue;
		
		find(next.first, now);
		
		for(int j = cnt[now]; j >= 1; j--){
			fk(1, cnt[next.first]+1){
				if(j + k > need) break;
				
				dp[now][j+k][1] = min(dp[now][j+k][1], dp[now][j][1]+dp[next.first][k][1]+next.second*2);
				dp[now][j+k][0] = min({dp[now][j+k][0], dp[next.first][k][1]+dp[now][j][0]+next.second*2, dp[now][j][1]+next.second+dp[next.first][k][0]});
				
			}
		}
		
		cnt[now] += cnt[next.first];
	}
	
	return;
}

int main(void){
	scanf("%d%d%d",&n,&need,&x);
	fi(0,n+1) vec.push_back(pushvec);
	
	fi(1,n){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		vec[a].push_back({b,c});
		vec[b].push_back({a,c});
	}
	
	find(x, x);
	
	printf("%d\n", dp[x][need][0]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

museum.cpp: In function 'int main()':
museum.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d%d",&n,&need,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20