글 읽기 - 20 % 에서 시간이 초과 됩니다. (반례 없습니다.)

sinse100 5년 전 0

제가 이문제를 푼 방법은 다음과 같습니다.

테스트 케이스가

1

8 8

10 20 1 5 8 7 1 4

1 2

1 3

2 4

2 5

3 6

5 7

6 7

7 8

7

라고 주어졌을 때

각각의 건물을 정점으로 하고 그 사이를 선행관계를 나타내주는 간선을 가지는 방향그래프로 설정하였습니다.

그리고 최단 시간을 구하기 위해

정점 7 부터 시작하여 (최단 시간을 구하는 함수를 EarliestEvent 라 했습니다.)

EarliestEvent(7) = 7번 건물 짓는 시간 + max(EarliestEvent(5),EarliestEvent(6))

또

EarliestEvent(5) = 5번 건물 짓는 시간 + EarliestEvent(2)

이런식으로 재귀가 이루어지도록하다가 진입차수가 0 인 정점에서는

해당 정점의 번호의 건물을 짓는 시간을 반환하도록 하였습니다.

또한, 그래프 객체를 정의하였는데, 그래프 객체(AOE) 는 입력된 정점의 개수와 같은 NetworkNode로 구성되어있습니다.

그리고 NetWorkNode 객체는 해당 건물의 번호, 그리고 해당 정점으로 들어오는 진입차수의 소스(몇번 정점에서 들어오는가??)들을 담을 벡터,

그리고 작업 시간으로 구성되어있습니다.

제가 생각하기에는 최상의 알고리즘 같은데 자꾸 시간이 초과 되네요......

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;

class NetworkNode
{
friend class AOE;
private:
int No;
int cost;
vector prev; 
public:
NetworkNode(void): No(0), cost(-1), prev() {}
void setCost(int c) { cost = c; }
void setNo(int n) { No = n; }
void addVertex(int v) { prev.emplace_back(v); }
};

class AOE 
{
private:
NetworkNode * graph;
public:
AOE(int edge) : graph(new NetworkNode[edge]) 
{
for (int i = 0; i < edge; i++)
graph[i].setNo(i + 1);
}
void setCosts(int e);
void layout(int v);
int EarliestEvent(int w);
};

int AOE::EarliestEvent(int w)
{
if (!graph[w - 1].prev.size())
return graph[w-1].cost;

int a = -1, m = graph[w - 1].prev.size();

for (int i = 0; i < m; i++)
a = max(EarliestEvent(graph[w - 1].prev.at(i)), a);

return graph[w-1].cost+a;
}

void AOE::setCosts(int e)
{
int a;

for (int i = 0; i < e; i++)
{
scanf("%d", &a);
graph[i].setCost(a);
}
}

void AOE::layout(int v)
{
int prev, next;

for (int i = 0; i < v; i++)
{
scanf("%d %d", &prev, &next);
graph[next - 1].addVertex(prev);
}
}

int main()
{
int T;
scanf("%d",&T);
int * ee = new int[T];

for (int i = 0; i < T; i++)
{
int e, v, w;
scanf("%d %d", &e, &v);
AOE work(e);
work.setCosts(e);
work.layout(v);
scanf("%d",&w);
ee[i] = work.EarliestEvent(w);
}

for (int i = 0; i < T; i++)
printf("%d\n", ee[i]);
return 0;
}

djm03178 5년 전 0

이미 방문했던 건물을 또 방문할 수 있기 때문에 오래 걸립니다.

아래는 다이아몬드 모양으로 규칙이 길게 이어져 있는 케이스입니다.

1
120
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
3
4
4
5
6
7
7
8
9
10
10
11
12
13
13
14
15
16
16
17
18
19
19
20
21
22
22
23
24
25
25
26
27
28
28
29
30
31
31
32
33
34
34
35
36
37
37
38
39
40
40
41
42
43
43
44
45
46
46
47
48
49
49
50
51
52
52
53
54
55
55
56
57
58
58
59
60
61
61
62
63
64
64
65
66
67
67
68
69
70
70
71
72
73
73
74
75
76
76
77
78
79
79
80
81
82
82
83
84
85
85
86
87
88
88
89
90
91
91
91

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