jzoj 1274. 여행 코스 (lines.pas/cpp)

13606 단어 DP
이 문제 DP, 시험장 때 수조를 작게 열었어...f[i][j]를 설정하면 제j일에 도시 i에 도착하는 데 가장 적은 비용을 쓴다.f[n][m]를 출력하면 됩니다.시간 복잡도 O(n2m) 위 첨자:
#include
#include
#include
using namespace std;
int n,m,a[110][110][21],x;
int c[110][110],f[110][210];

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

int main()
{
	freopen("lines.in","r",stdin);
	freopen("lines.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			if (i==j) continue;
			c[i][j]=read();
			for (int k=1;k<=c[i][j];k++)
				a[i][j][k]=read();
		}
	memset(f,10,sizeof(f));
	f[1][0]=0;
	for (int k=1;k<=m;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
			{
				if (i==j) continue;
				x=a[i][j][(k-1)%c[i][j]+1];
				if (!x) continue;
				f[j][k]=min(f[j][k],f[i][k-1]+x);
			}
	if (f[n][m]==f[0][0]) puts("0");
	else printf("%d
",f[n][m]);
	return 0;
}
루비 초보자 과제 return 역할 영역 방법
GitLab 코드 검색 도구를 만들었으니 사용해 보세요

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage