제출 #132952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132952		StevenH	경주 (Race) (IOI11_race)	C++14	9 / 100	35 ms	2808 KiB

race

#include "race.h"
const int maxn=1005;
struct Edge{
	int to,dis,next;
}edge[1005];
int head[maxn],edge_num;
void addedge(int from,int to,int dis)
{
	edge[++edge_num].to=to;
	edge[edge_num].dis=dis;
	edge[edge_num].next=head[from];
	head[from]=edge_num;
}
int LL[maxn],KK;
int m;
bool vis[maxn];
int p,l,ans;
void dfs(int x)
{
	if(l>KK)return;
	if(l==KK)
	{
		if(p<ans)ans=p;
		return;
	}
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!vis[v])
		{
			vis[v]=true;
			l+=edge[i].dis;
			p++;
			dfs(v);
			p--;
			l-=edge[i].dis;
			vis[v]=false;
		}
	}	
	return ;
}


int best_path(int N, int K, int H[][2], int L[])
{
	KK=K;
	ans=N+1;
	for(int i=0;i<N-1;i++)
		addedge(H[i][0],H[i][1],L[i]);
	for(int i=0;i<N;i++)
	{
		p=0;
		l=0;
		vis[i]=true;
		dfs(i);
		vis[i]=false;
	}
	if(ans==N+1)return -1;
	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57