글 읽기 - ACM craft 제 코드에서 시간을 줄일 수 있는 방법은 없나요??

stiti 7년 전 0

3중 for문을 이용해서 i->q, q->j가 존재하면 i->j를 업데이트 해주는 방법으로 풀었습니다.

여러가지 testcase들을 찾아서 입력해보니 답은 맞게 나오는듯 하지만

처음부터 시간초과가 나옵니다.

이 문제는 제가 푼 방식으로는 불가능한 문제인 것인가요? 아니면 시간을 더 단축할 수 있을까요?

#include <iostream>
#include <vector>
#include <queue>	
#include <string.h>
#include <algorithm>
using namespace std;
int con[1001][1001];  //연결됨????
long long dp[1001][1001]; // i to j
int arr[1001];
int k, w, n;
int t;
int main()
{
	cin >> t;
	for (int test = 0; test < t; test++)
	{
		memset(con, 0, sizeof(con));
		memset(dp, -1, sizeof(dp));
		scanf("%d %d", &n, &k);
		for (int i = 1; i <= n; i++)
			scanf("%d", &arr[i]);
		for (int i = 1; i <= k; i++)
		{
			int s, e;
			scanf("%d %d", &s, &e);
			con[s][e] = 1;
			dp[s][e] = arr[s];
		}
		scanf("%d", &w);
		for (int q = 1; q <= n; q++)
		{
			for (int i = 1; i <= n; i++)
			{
				if (i == q)continue;
				for (int j = 1; j <= n; j++)
				{
					if (j == q) continue;
					if (con[i][q] == 1 && con[q][j] == 1)
					{
						dp[i][j] = max(dp[i][j], dp[i][q] + dp[q][j]); 
						con[i][j] = 1; // i->j는 가는 길이 있다.
					}
				}
			}
		}
		long long result = 0;
		for (int i = 1; i <= n; i++)
		{
			if (dp[i][w] == 0) continue;
			result = max(result, dp[i][w]);
		}
		printf("%lld\n", result + arr[w]);
//		for (int i = 1; i <= n; i++)
//			for (int j = 1; j <= n; j++)
//				cout << i << ' ' << j << ' ' << con[i][j] << endl;
//		for (int i = 1; i <= n; i++)
//			for(int j =1;j<=n;j++)
//			cout << i << ' ' <<j<<' '<< dp[i][j] << endl;
	}
	return 0;
}

sgchoi5 7년 전 0

3 중 for 문 이용하시면 시간 초과 해결이 안 되고, topological sort 로 검색하셔서 해당 알고리즘에 맞춰서 하셔야 합니다.

https://www.acmicpc.net/board/... 참고하세요. TC 가 공유되고 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

ACM craft 제 코드에서 시간을 줄일 수 있는 방법은 없나요??

stiti 7년 전 0

sgchoi5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말