OJ Board

Posted: **Mon Aug 23, 2004 7:43 pm**

Haven't found any topic about this problem. It must be one of the easier ones. but still I could not find any solution to this problem.

For this problem,
I assume that there will not be any circle in the given graph and there will atleast be one node which will not have any preceding node (I call it starting node). I run DFS() from all the starting nodes and update the costs of the tasks/nodes connected to it.

Where is my mistake. anyone plzzzzzzzzzz help.

Posted: **Tue Aug 24, 2004 11:59 am**

I faced with the same problem as you. I think that your method is good - I can't imagine any case which could causes failure of such algorithm.

If anyone should help us and post some critical IO or proof that this approach isn't good - we would be greatful

I test my program with cases where exist more than one separate graph in input and so on, but I still got WA.

Best regards
DM

Posted: **Sun May 08, 2005 7:51 am**

Wow. This problem has a crazy amount of input! I did a very lazy topological sort using Floyd-Warshall, and it timed out, even though it's a O(n^3) algorithm with n=26. Then I replaced all the instances of getline() with gets() and used a O(n^2) insertion sort instead of Floyd-Warshall and got accepted in 8.6 seconds. Unbelievable! I wonder what the size of the input file is. It must be at least 10 MB.

Posted: **Mon May 22, 2006 3:25 pm**

I think they have repeated lines in the input.

For example:

Code: Select all

1

A 5
A 5
A 5
.... ( the line A 5 is repeated 2000 times for example ... ) 
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC
E 4 DC
E 4 DC
.... (the line E 4 DC is repeated another 3000 times ... )

I got ACC in about 0.4 sec.
I don't think the input is so hard.
I don't know for sure of course.

Here is a small advice. What I do is...
Well... When I see a line starting with the char 'A' and
I've had already in the same test case a line starting with 'A'
('A' is just an example) I just ignore this second
occurrence of the 'A'-line.

So I don't think the input contains something like
...
A 4 BC
A 4 DE
...
because such an input would screw up my logic.

Good luck.

Posted: **Tue Mar 03, 2009 4:38 pm**

I have a problem with example 452. I get a runtime error. Can someone tell me what should I look for at input and output?

I also need to know if the graph includes a cycle what do I get on system output?

Thank you.

Posted: **Tue Mar 03, 2009 7:09 pm**

Most of the times RE means you are accessing memory
which your program did not acquire first. For example
you may be trying to access element i=1001 of an array
having len=1000 elements.

Posted: **Mon Apr 26, 2010 6:57 pm**

Solaris wrote: For this problem,
I assume that there will not be any circle in the given graph and there will atleast be one node which will not have any preceding node (I call it starting node). I run DFS() from all the starting nodes and update the costs of the tasks/nodes connected to it.

Where is my mistake. anyone plzzzzzzzzzz help.

The graph must be a DAG.
SO there have no circle.
There can be multiple starting node.
There can be Multiple DAG in a case.

Posted: **Mon Aug 29, 2011 9:51 pm**

try this case:

Code: Select all

[b]1

A 2
C 3
B 5 AC
D 10 B
H 13 GF
E 11 B
G 12
F 2 DE
I 10
J 20 I
[/b]

output from my ac code:

Code: Select all

Posted: **Wed Jun 26, 2013 9:30 am**

Could someone please provide some test cases/help me debug?

I tried a few of my own but I keep getting WA...I'm not sure what the issue is. My code works for all cases above.
I tried using bellman ford initially and now i'm using dfs, but I can't get either AC.

Edit: Got AC

Thank you in advance.

Posted: **Wed Jun 26, 2013 10:37 am**

don't read from a file.
print a newline at the end of the last line.

Posted: **Wed Jun 26, 2013 10:57 am**

Wow, I can't believe it was so simple.

Thank you!

Posted: **Thu Jun 27, 2013 9:23 pm**

Getting WA...plzz help

Code: Select all

AC

Posted: **Thu Jun 27, 2013 11:40 pm**

Input:

Code: Select all

100

A 52
B 98 A
C 68 A
D 97
E 9 C
F 37 CDE
G 69 DEF
H 42 E
I 5 CEGH
J 60 BFGI
K 76 CEFGHJ
L 55 ABFHK
M 33 BCDEHJ
N 96 ABCDEFIM
O 33 ABCHIN
P 98 BCGHJLN
Q 11 BEFHKLOP
R 91 ABCDFHIJKMNQ
S 13 CDEKLM
T 57 CDEFLPQS
U 13 ABCFGHIJLMNPQST
V 5 ACFGHJPQRST
W 2 BCDFGHKOQRSTUV
X 93 CDEGJKMOPQRT
Y 94 ABCEHJMPQRSUW
Z 92 BEHILNOPQRTUY

A 76
B 30
C 70
D 34 BC
E 52 ACD
F 82 CDE
G 9 AF
H 99 ACDFG
I 53 ABDEFG
J 2 DH
K 37 AEGHJ
L 14 ADEFHJK
M 6 ADEFGIJL
N 85 BJ
O 79 BGIKLMN
P 9 ACKLNO
Q 83 ACDEHIJLNP
R 9 BCEIJMOPQ
S 14 BCDEJMOR
T 6 BCEFGHKLMQ
U 67 EHIJLNOPQST
V 39 IJKLMNQRSU

A 2
B 37
C 16
D 43 ABC
E 20 AB
F 29 ABC
G 36 ADEF

A 35
B 20
C 72
D 70 BC
E 2 BCD
F 90 ABC
G 77 EF
H 98 BCEF
I 47 ABE
J 7 DHI
K 76 ADFHJ
L 13 ADEFGHK
M 8 ADFI
N 83 ABDFHJL

A 79
B 57
C 87
D 48 AC
E 8 D
F 67 AD
G 90 ACDF
H 54 DFG
I 90 ABDEFGH
J 84 BGHI
K 50 BDEGHI
L 94 ACEGJK
M 63 ABCFGHIK
N 91 ABFKLM
O 77 AEGHL
P 42 HMNO
Q 76 BCEFGIKLNO
R 71 AFIJKQ
S 78 ADEMNOPQR
T 47 DEFGHIJ
U 24 GHIJLMNT
V 93 BDEGHJKLOQSU
W 69 ACFHIKLMORT
X 7 ACEFGIJLMNORSTU
Y 49 CDFGILMNORSTUWX
Z 30 ABCDEGHLMOPSTUVWXY

A 80
B 73 A
C 77 A
D 96 B
E 31 BCD
F 93 CD
G 77 ABDF
H 86 ABDEF
I 33 BCFGH
J 8 ABCEF
K 2 ADFGHJ
L 71 BDEIJK
M 3 DGJL
N 67 BHJL
O 86 BDEGK
P 17 ACFJKLMO
Q 98 EGHJMNOP
R 31 BCHIJKLMNOPQ
S 59 ABCEGHKLMNQ
T 42 ACDEJKLPQR
U 88 ACEFHJMNOR
V 52 ABCDHOPST
W 9 FJKLNORSUV
X 50 CEGHIJKLMNPQRW
Y 54 CDEGHKMOQSUVW

A 48
B 88 A
C 14 AB
D 92 ABC
E 86 ABC
F 93 ADE
G 22 ABDEF
H 15 ACEFG
I 41 ABDEFH
J 3 ACE
K 74 BDJ
L 2 ACDEHIK
M 89 ABCEFIJ
N 97 EGIKLM
O 41 ABFGJN
P 18 ABCDEFGHIJLN
Q 49 BCDIJKLP
R 47 AEFGIJKLMOP
S 60 ACDEHJKLPR
T 34 DEFHJKLQ
U 42 ABCFHKNOPRT
V 65 CFGKLMOPS
W 17 BDFHKNOPQRSTUV
X 45 CDEGNPVW

A 59
B 79 A
C 8
D 5
E 29 AD
F 13 ABCD
G 83 ACDF
H 61 DEG

A 85
B 89 A
C 35 A
D 18 ABC
E 40 D
F 27 AB
G 91 ACDEF
H 67 D

A 58
B 88
C 93
D 37 B
E 55 AD
F 19 ABD
G 93 DE

A 64
B 40 A
C 52
D 32 ABC
E 44 ACD
F 22 D
G 17 ACD
H 51 BCFG
I 98 ACG
J 81 ACDH
K 70 AG
L 89 ABCGH
M 8 IKL
N 86 ADHIJKL
O 16 ACFIM
P 17 EFHLMO
Q 60 ABCDIKLN
R 98 BCEHJKNP
S 59 ACEGHKOPR
T 3 DEGORS

A 21
B 35
C 92
D 9 A

A 30
B 75 A
C 69 B
D 10 AC
E 23 BD
F 71 BD
G 95 ACF
H 98 CDE

A 13
B 79
C 44
D 49
E 96 ACD

A 3
B 44 A
C 21
D 71
E 30 ABD
F 20 AD
G 65 CEF
H 86 ACDEG
I 41 ABCEGH
J 6 ADI
K 87 EGJ
L 5 ABCDEGJK
M 24 AGHIJKL
N 75 ABCDFGHM
O 16 BCDFGIKMN
P 61 CDEIJLNO
Q 24 AFHILMNOP
R 1 BCEFJLNQ

A 47
B 14 A
C 22 AB
D 6 A
E 0 AB
F 72 B
G 2 CEF
H 35 DE
I 16 BEH
J 74
K 99 ACFHI
L 48 ACEFHK
M 74 CFGJK
N 47 CDFGHJLM
O 35 BGIJKLM
P 76 EGIO
Q 71 CHIJN
R 95 BGJNP
S 35 ACEGHKLMP
T 97 CDHJKLPQ

A 75
B 78
C 76 A
D 48 B
E 87 A
F 76 CDE
G 68 DE
H 7 ABDE
I 96 CEH
J 64 CDEH
K 22 BFHIJ
L 37 ABCK
M 64 ACHIKL
N 68 ABFGIJLM
O 96 ABCDEHJKLN
P 81 AGHIJMO

A 89
B 66 A
C 55 AB
D 57 B
E 56 AC
F 1 AD
G 65 ABDEF
H 43 CE
I 50 AF
J 79 BCEFG
K 57 ABDEH
L 1 BEG
M 62 ACEFJL
N 2 BEFGHIJM
O 34 BEGHILMN
P 25 GHIKLMN
Q 9 ABGLMNOP
R 75 ABCDEFGHLP
S 88 IJKMQR
T 9 CEHIKLNOR
U 2 BCDFGHLOPT
V 64 ABDGJLNPRSU
W 32 ABGHMNQSTUV
X 53 ACIJLMPRS
Y 57 ADHJMOQRT
Z 29 ABEFGILNQSTUWX

A 91
B 30
C 27 B
D 64 B
E 33 AD
F 94 C
G 83 BEF
H 17 ABEF
I 51 EFH
J 61 BCDEF
K 19 DEGHI
L 87 CDJ
M 83 CDFHI
N 75 BCDEJM
O 9 BCEFGHKLMN
P 33 ACEFGIJO
Q 25 ADHLMNO
R 57 CDEFHIKL
S 47 CDFGKNPQ
T 86 ABCIMNQR
U 35 GHIJKQ
V 11 DGLMOPQR
W 74 BCFJNOPQRTV
X 95 CDFGKNOQSW
Y 78 AEFGHILNORVWX

A 16
B 31
C 38
D 19 AC

A 65

A 99
B 94 A
C 61 AB
D 56 B
E 41 ABCD
F 18 A
G 72 AC
H 8 ACDE
I 78 BCDF
J 90 BEFI
K 21 CEFGHIJ
L 53 ADEFHIK
M 92 BCDEGJKL
N 76 CDFGIK
O 94 ACDGIJKLM
P 22 DGHIJLNO
Q 22 BCEFGHLMO
R 7 ABCDHJKLNP
S 72 ABCEFGJKOPR
T 69 EFILMNPR
U 82 CJKNPQR
V 39 FJ
W 13 BCDGHIKLNOQRSTU
X 44 AEJKOPQRTUV
Y 6 ABCFHJKLMNOQTV

A 46
B 73
C 33 A
D 38 C
E 8 ABCD
F 6 AE
G 96 AF
H 96 DE
I 33 CDFG
J 88 ABCDEGH
K 79 ABCEFH
L 77 BDHJK
M 19 CGHIL
N 33 H
O 39 ABEFGIJKMN
P 37 CEFGHKN

A 72
B 38
C 85 AB
D 24 A
E 58 ABC
F 37 BD
G 49 CD
H 54 ACD
I 38 FG
J 69 ADEFHI
K 63 CEFGJ
L 20 FIJK
M 29 DFHIKL

A 2
B 71 A

A 12
B 38
C 42 B

A 99
B 53 A
C 22
D 51 C
E 15 D
F 99 CE
G 68 ABDF
H 6 ACE

A 79
B 15 A
C 73 B
D 73 C

A 57
B 22 A
C 84
D 45 C
E 1 CD
F 34 BCDE
G 60 DEF
H 44 CEF
I 29 BCF
J 49 AFI
K 90 BCEFG
L 52 CDGH
M 72 FGIL
N 12 AJK
O 8 EGHMN
P 62 BEHKLMN
Q 77 ACEFGIJK
R 35 FINQ
S 28 CGJNQ
T 54 CFIKLNPQ
U 9 FHKMPQST
V 23 CEGHIJLMOQTU

A 90
B 77 A

A 45
B 92 A
C 64 A
D 58 C
E 95 AB
F 31 ABCE
G 38 AE
H 46 CFG
I 12 ADEFH
J 30 ACFGHI
K 95 CGH
L 38 BFGJK
M 44 ACEGJK
N 41 ABDEFGHIJKLM
O 70 ACEFGHJN
P 60 BCEFGNO
Q 96 BCEFGIJKMP
R 5 ABCEFGHIJKNOPQ
S 69 CDEHIKNPQR
T 90 DGHIJLM
U 25 ABCDEGIMOPQR
V 20 ABCDEGHJLQSU
W 89 ABCHJLMOQSUV

A 46

A 89
B 72 A
C 99 A
D 40 AB
E 69 ABD
F 30 ABCD
G 22 CF
H 8 EF
I 82 BCFGH
J 44 CDEGH
K 59 H
L 49 DIJ
M 37 BEGJ
N 42 BCEHK
O 21 BCDFKN
P 72 BDFIJLM
Q 48 BEFIKLO
R 61 ACFIJKMNPQ
S 44 EKLNOPQR
T 61 ABDIJKLQ
U 62 ABCEGKLRT
V 14 BEFGHIJMOPQSU
W 19 BCGHIJLMNQTV
X 34 CFGHIJMNOSTU
Y 59 ACDGILPQSUX
Z 48 ABCEFGHKLMRUVWXY

A 21
B 59
C 22 B
D 59 AB

A 77

A 25
B 95 A
C 0 AB
D 26 ABC
E 65 D
F 97 ABDE
G 93 AF
H 67 AEG
I 40 DEG
J 67 BDFH

A 90
B 48 A
C 9 A
D 53 ABC
E 89 BC
F 90 ACDE
G 49 DE
H 38 ABDF
I 32 DE
J 94 BDFGHI
K 31 BFGI

A 6
B 7
C 62 B
D 30 A
E 81 AC
F 85 BCDE
G 36 AB
H 94 ABE
I 27 BCE
J 34 ACEH
K 15 ACDEGHJ
L 44 ABCEHJK
M 42 BDFGHJ
N 55 ABDE
O 97 ABDGHLMN
P 95 AEFGHIKL
Q 89 ABELM
R 36 ABCFJMOP
S 6 DGHJKOPQ
T 38 ACEFHIJKLMNOQR
U 8 ABCEGHIJKPT
V 83 ACEFGIJLQRSTU
W 29 ABEJLMNSUV

A 37
B 66 A
C 65 A
D 78 ABC
E 45 ABCD
F 21 AE
G 79 ABCDF
H 88 BCEG
I 29 CEGH
J 46 EI
K 35 ACDIJ
L 61 ABEFK
M 43 ABDEHI
N 84 EGHJLM
O 61 DEFGIJN
P 96 BIJMN
Q 86 AEGHIKLO
R 66 ABEGKLO
S 3 ACEFGKNOQ
T 40 FMNOPS
U 37 BDEFHJKLMNOPST
V 72 BDFGKLMRST
W 18 ABCFHMOSTU
X 41 DEFHJKLMOR
Y 8 ACEFHKLMNOSX

A 51
B 45 A
C 9 AB
D 88 ABC
E 57 B
F 75 AE
G 10 ABCDEF
H 23 EG
I 59 BD
J 77 ACHI
K 94 CEHI
L 16 BCFGH
M 88 ADEH
N 97 BEFJK
O 62 EFLM
P 57 AHLMO
Q 41 BFIJNOP
R 99 ACDFIJLMNOQ
S 31 ACDEHJKP
T 74 CDIJKPQS
U 25 ADGJM
V 75 ACDFGHLNORST
W 81 CIKLMNU
X 5 ABCHIKLMNPTUW

A 14
B 10
C 29 AB
D 34
E 79 CD
F 17 CDE
G 23 CDE
H 19 ACDE
I 40 ABDGH
J 75 ABFGHI
K 32 BDFHJ
L 91 EJK
M 89 ABDFIJK
N 53 EHL
O 41 ABEJL
P 80 BDN
Q 17 BDGJKLMNO
R 54 ABDEGHIJMNOPQ
S 42 ABCGHKOP
T 85 ADFHJKMOP
U 92 CFGHIJKLMNPS
V 8 CGJPQSU
W 24 DEHLMORSUV
X 66 CEFGHIJKLOUW
Y 13 BFIJLNQSTW

A 37
B 60 A
C 31
D 13 AC
E 1 ABD
F 10 C
G 35 A
H 16 ABCDFG
I 77 CFG
J 64 DHI
K 76 BFG
L 85 ABEGJ
M 2 ABCEGH

A 87
B 24 A
C 77
D 44 AC
E 6 C
F 48 ABCD
G 25 EF
H 22 ACDEF
I 47 ABGH
J 13 AE
K 68 BCEFG
L 22 HIJ
M 67 ABCDEFHIJKL
N 84 CDEFGHIJKLM
O 83 BCGILMN
P 46 EFGLNO
Q 11 FGJLO
R 80 CDFIJLNO
S 21 ABDEFHILOPR
T 76 DFLMNOPS

A 79
B 83
C 70 A
D 99 C
E 26 B
F 59 ACD

A 58
B 82
C 47 AB
D 51
E 85 D
F 52 BC
G 38 ACF
H 28 EG
I 90 ABF
J 50 CDEFGI
K 19 BGIJ
L 18 ACGHJK
M 3 BGHJKL
N 17 CDEFGHIJL
O 11 ABEFHKLM
P 61 BCGIK
Q 59 ABEFIJKLN
R 60 ACDEFGHJNOPQ
S 55 BDFHIKLOP
T 60 ABEHLNOP
U 19 ACFGIJMNOQRST
V 53 BDFGHIJLNPS
W 53 ABDEGIJKLOQSTV
X 42 CEFHKLMNPQRSVW
Y 12 CDJOSTWX
Z 57 BCDEFGHKNOPQRSTVY

A 12
B 79
C 39
D 33 B
E 7 BD
F 20 BCDE
G 36 CF
H 61 ABCEF
I 4 CG
J 65 AF
K 69 ACEGHI
L 29 ADGH
M 36 FK
N 81 ABFIJKL
O 22 ACFJM
P 99 ABDEGHJLO

A 55
B 27
C 3 B
D 90 BC
E 27 ABC
F 96 ACE
G 98 ABE
H 48 BCEF
I 69 AEGH
J 44 CDI
K 84 EGHI
L 31 BCDFGHJK
M 70 BEHK
N 61 ADFGIM
O 91 BCEIJM
P 71 CIKNO
Q 20 ACDFGO
R 54 CFHKLMN
S 73 BEFHIKLMNOR
T 89 CGHJLMNOPQS
U 18 ACEFGHIJLMNOPQST
V 74 ACEFGKMOQS
W 48 BCDHJKLNPQRSUV
X 38 ABDEHJKNPQSW
Y 35 ACDEIPQRSTVWX
Z 57 BCFGOSXY

A 57
B 48
C 56
D 3 A
E 28 A
F 52 CE
G 23
H 49 ABDG
I 2 ABCDE
J 34 CDG

A 20
B 42 A

A 87
B 2 A
C 32 B
D 84 ABC
E 8
F 36 ABC
G 1 B
H 2 ACEF
I 49 ABEG
J 35 ABEH
K 72 ADJ
L 32 ABDEFGI
M 78 CDGIJK
N 51 ACDHJLM
O 93 ABCDFGHJMN
P 59 ABCIJMO
Q 76 ABCEFGIJLNOP
R 92 BCEFGMO
S 83 ABCDGHJLMOQ
T 10 BEHIKOPRS
U 48 ADEFMORT
V 67 ABCEFMNOQRTU
W 30 ABCDEGJLMNPQTV
X 38 BCDEFGHKLNOQTUVW
Y 54 AFGLMNOPQSTUX
Z 46 CEFGHJLPRTWY

A 22

A 38
B 71 A
C 95 A
D 89 B

A 1
B 29
C 99
D 53 AB
E 11 BCD
F 65 CD
G 10 BC
H 52 C
I 16 ABCG

A 8
B 46 A
C 48
D 10 B
E 49 C
F 78 D
G 60 B
H 17 BE
I 15 BH
J 17 BCGHI
K 15 ABCDEGIJ
L 4 BCDFGK
M 8 BFGHIJ
N 70 ABFGHKM
O 90 CGIKM
P 79 ABEIKLMNO
Q 61 ABEFGHJMNO
R 56 ABCEGHIJKOPQ
S 87 DGILNQ
T 74 ABCFHJMS
U 32 ADGIJMNPT
V 71 BEJKMPRSTU
W 65 BEJKMNOQRSU
X 39 ACEIJLNOPQTV

A 94
B 19 A
C 35 B
D 26 BC
E 54 BD
F 48 ABC
G 67 ABCDEF
H 9 ABCDG
I 62 BCDG
J 69 ADFH
K 45 BCDEGIJ

A 63
B 26 A

A 35

A 30
B 76 A
C 51 B
D 26 ABC
E 19 BD
F 69 AE
G 32 ABCE
H 8 BCDEG
I 68 DEGH
J 79 BEF
K 11 BFGH
L 0 ADFGHJK

A 71
B 43
C 94 A
D 5

A 89
B 60
C 18 A
D 42 ABC
E 23 B
F 20 ABC
G 68 ACDEF
H 22 CF
I 16 BDEH
J 10 CDEFG
K 50 ABCDEFI
L 82 CEHJK
M 90 CEFHIJ
N 63 BCDEFGHJL
O 69 ABDEGHIKMN
P 62 DEIJLMNO
Q 16 EGHIJLMNOP
R 17 GHIMOP
S 37 AEFKLMNOQR
T 30 ACDGIMPQR
U 53 CDEGHLMNPQR
V 60 CDFILMNPST
W 28 BCDEGHMOPSU

A 47
B 52
C 15 AB
D 17 BC
E 7 AC

A 28
B 42 A
C 58 A
D 9 AC
E 98 ACD
F 33 ABCE
G 66 CDEF
H 3 BCF
I 66 BCDEG
J 49 BDF
K 7 BCDEJ
L 50 ABCHIJK
M 48 ABDEFGIK
N 26 AEGIJLM
O 93 DEFGKLM
P 36 ADIKO
Q 49 ABFGHLMOP
R 48 ADEHIMNOQ
S 93 ABEJKLMNO
T 30 ADGHIJKQRS

A 53
B 8
C 62 AB
D 97 A
E 82 A
F 4 BCDE
G 90 ABDF
H 54 ACDEF
I 80 ADFG
J 94 ACEG
K 41 ACEFGJ
L 36 ADEGJK

A 60
B 15 A
C 67 B
D 85 BC
E 63 A

A 11
B 17
C 8 AB
D 75 B
E 76 BC

A 87
B 4 A
C 17 A
D 37 B
E 97 ABD
F 62 ABD
G 49 AF
H 31 B
I 86 ACG
J 67 ABCDFI
K 82 BDF
L 84 BCEFIK
M 86 ACEFHIJK
N 63 ADGIJK
O 0 ACEGHIKMN
P 20 ACHILNO
Q 52 BCFGHJKLO
R 46 CGHKLMN
S 84 FGHJM
T 20 BCHLMOP
U 50 BFHIJKLPQT
V 78 CEGJLMNQR
W 75 ABCFHJLMNQSV

A 46
B 77
C 51 AB
D 39 A
E 16
F 20 BDE
G 63 ABCEF
H 40 DFG
I 39 CDFG
J 48 ACDGH
K 8 ABCDEFGI
L 13 ABCHK
M 69 ACEHJL
N 88 ABDEIL
O 64 CDFIN
P 51 BDEFHIJKM
Q 25 BDEGHIKL
R 19 ABHILP
S 81 CDEFHIKMOQR
T 18 ACDEGHJKMOPQS
U 20 ADEGHIKMOQRST
V 40 BCNOPRT

A 30
B 7
C 36 B
D 27 ABC
E 33 ACD
F 84 BE
G 71 AB
H 63 BCDFG
I 31 BCDGH
J 73 ABCEGHI
K 33 ABCFGHI
L 57 DEGHIJ

A 24
B 80
C 70 AB
D 0 C
E 94 BCD
F 69 BE
G 40 BDF
H 44 DEF
I 80 ABCEF
J 87 ADGI

A 50
B 49
C 94 AB
D 15
E 55 BD
F 53 ABCD
G 18 ACD
H 66 AB
I 43 ACDEFH
J 71 DE
K 27 BFHI
L 73 CDEFG
M 79 BEFHIJKL
N 88 BCEHIKM
O 63 ABCEHJKLN
P 96 ABIJKL

A 27
B 31
C 17 B
D 23 ABC
E 78 BC
F 27 CE
G 43 CEF
H 76 ABCE

A 47
B 11 A
C 20 AB
D 64 ABC
E 21 D
F 26 BC
G 70 BCDEF
H 97 ABCEFG
I 60 AG
J 75 AEHI
K 54 ACEGHIJ
L 82 CEFIJK
M 15 ABDEHIL
N 81 ABIK
O 59 ABDFGHIJKN
P 85 DGHIJLMN
Q 38 BCDGHIKMOP

A 75
B 46 A
C 39 A
D 90 B
E 49
F 93 ACDE

A 23
B 91
C 17
D 96 ABC
E 79 AD
F 5 AC

A 16
B 1
C 69 A
D 47 B
E 23 ABD
F 87 ABD
G 76 ABC
H 47 BCDF
I 54 CG
J 13 B
K 56 DG
L 82 CDFGHIK
M 78 ABCDEFGHIJL
N 40 IJ
O 29 AEFGHM
P 32 LO
Q 55 BCEGIJLOP
R 42 ABDFGIKLMO
S 91 ADEFKLMPQ
T 20 BCFGMNPS
U 23 BDFGLMOPQRST
V 95 BDFGMNU
W 43 ABCHIKLMNOQRSTU
X 32 FGKLNORST
Y 44 ACEFHIMNRS
Z 35 ABCDFIKNPQXY

A 99
B 51 A
C 83 B
D 76 A
E 21 AD
F 86 CE
G 48 BF
H 19 ADEFG
I 34 BCG
J 11 ACEH
K 30 CDEFIJ
L 74 ABCFHI
M 67 AL
N 89 ABEIM
O 73 ABCFGIJM
P 48 CGJKNO
Q 41 CEGHM
R 56 ADEGIMQ
S 45 ABEFHJKMNR
T 64 GIJKNPRS
U 18 CGILOPQS
V 2 AFILOQRS
W 84 CDEGHKRSV
X 4 BDEGHKMNOPQRTUW

A 58
B 80
C 50 AB
D 7 ABC
E 4 BD
F 53 CDE
G 74 CD
H 69 AG
I 52 ACFG
J 90 ACGI
K 50 ABCDFGIJ
L 45 ABCEGH
M 99 ACDEFIJK
N 66 BDGHIJKLM
O 92 BDHJN
P 59 BCDIJKLN
Q 40 ABEFIJL
R 69 ACDFGHIOPQ
S 45 CEGJLNOR
T 41 ADGHIOPQ
U 75 BCDEHJKNORST
V 51 ADEFHIJNORST

A 35
B 81
C 42 AB
D 3 ABC
E 87 A
F 33 BE
G 43 ACDE
H 55 ABD

A 40
B 11
C 97 B
D 53 AB
E 73 BCD
F 70 CE
G 74 ABCDF
H 94 BEF
I 45 BDFH
J 24 DGHI
K 33 BEFHIJ
L 80 CEGHIK
M 43 CGHIKL
N 34 ACEFHIL
O 31 FGHIMN
P 55 BJKLO
Q 79 BEFKMOP
R 73 CFGHKMNOQ

A 83
B 86 A
C 18 B
D 23 C
E 81 C
F 3 CDE
G 37 ABF
H 8 ACDFG
I 17 BDG
J 94 AEFG
K 49 EFGIJ
L 15 BEFIK
M 15 BEJK
N 44 BCDGIK
O 79 ABCEHIN
P 91 BCDHILM

A 17
B 41 A
C 85
D 3 BC
E 14 ABC
F 21 BDE
G 82 BF
H 66 CDE
I 57 ACGH
J 35 BGI
K 79 BCFGHJ

A 12
B 34 A
C 69 B
D 69 A
E 99 B
F 55 ABE
G 11 ACEF
H 21 ACD

A 27
B 35
C 84 A
D 37 A
E 18 AD
F 69 BC
G 88 ABE
H 48 AG
I 88 ADGH
J 53 BDEGH
K 88 AB
L 72 BDFGHK
M 31 BFIJKL
N 63 ABEJL
O 43 AFGHKMN
P 23 CDFIKLO
Q 55 FGHIKMO
R 84 BCDFGKLMOP
S 65 CDEFHKMNQ
T 69 EFGJLMRS
U 97 BILMOQT
V 17 ADEFGJLMNPQ
W 29 ADEFJKLSTU
X 34 ACFJNPRTUW

A 98
B 85

A 72
B 91 A

A 1
B 79
C 81
D 91 AB
E 83 BCD
F 83 BDE
G 33 ABDEF
H 20 BCDEF
I 33 BCFH
J 98 ABCGHI
K 56 ACDEGI
L 32 CDEFH
M 9 ADFGJK
N 4 ABCEFHI
O 87 ABK
P 13 BDHILNO
Q 74 EGHIJLMO
R 41 ABCFGIM
S 35 ABFHP
T 62 ADHIKMPRS
U 90 AHLRST
V 3 ABCDEPRSU
W 9 BCHJKLOQRTUV

A 53
B 90 A
C 61 AB
D 52 B
E 16 AD
F 49 DE

A 47
B 15
C 84 B
D 0 AC
E 69 A
F 19 ABCD
G 75 AF
H 15 ADFG
I 43 ACEGH
J 68 CDEFHI
K 82 ACEFGI
L 47 BCDEGJ
M 64 BEFGJK
N 83 ABCEFGL

A 61
B 65 A
C 77

A 88
B 92
C 79
D 69 AB
E 58 BC
F 38 C
G 68 BC
H 4 F
I 59 H
J 96 BCDFG
K 90 CEFHI
L 12 EGHJK
M 69 BCHJL
N 98 ABCEFGIJK
O 92 CDGIJKM
P 96 CEFGHJ

A 56
B 22
C 54 A
D 45 AB
E 26 ABD
F 12
G 99 ACDF
H 26 AD
I 24 ADFGH
J 27 ABCDEF
K 39 CEFHIJ
L 13 ACDGHI
M 86 ABDEGHJ
N 93 ABFGIJL
O 63 CEJKLMN
P 75 DGHIJN
Q 19 ACFIJMNOP
R 23 ACDEGIJQ
S 96 DGIMNQR
T 84 BCDGKNPQ
U 68 ADEFGHNQRT
V 13 ABFNPQRTU
W 44 ABDGIKLMNOPRSUV
X 57 ADHIJKLNQRSVW
Y 49 ADFHIJMNOSX

A 98
B 55 A
C 49 A
D 96 AC
E 93 ABC
F 74 ACE
G 38 ACDF
H 96 AEFG
I 81 ABCGH
J 23 BCDEFGI
K 39 BFJ
L 42 CDFHIJK
M 62 BCDHJ
N 83 ADEGHIJKM

A 27
B 94
C 41 B
D 39 BC
E 86 ABD
F 31 ACDE
G 44 ABC
H 9 ADG
I 69 ABCG
J 59 BCDEGI
K 14 ABHI

A 74
B 55
C 51 A
D 33
E 48 BCD
F 34 BC

A 80
B 68 A
C 13 AB
D 18 A
E 15 D
F 29 ABDE
G 15 ACDF
H 32 DEF
I 66 ABFH
J 4 ACDEFGI
K 12 BCFHI
L 11 ABEFGHJK
M 76 CDEGK
N 46 ACGIJK

A 36
B 17
C 12
D 93 AC
E 18 BCD
F 55 AD
G 12 AE
H 64 BDEG
I 21 BCDEFG
J 95 CEG
K 35 ABCDEHI
L 74 ACFHIJK
M 87 EFL
N 77 BFGJLM
O 9 ACEFGH
P 24 ABCDFGHJKLNO
Q 45 BFGIJMP
R 31 ACELMO
S 73 ACDEGHJLNO
T 76 EFGHKMNOQRS

A 39
B 76
C 80
D 79 C
E 25 CD
F 63 AD
G 37 ABCE
H 58 CEG
I 91 ABCDFG

A 14
B 95 A
C 94 B
D 31 B
E 46 D
F 23 B
G 95 AF
H 41 CDEF
I 78 ACDH
J 75 ABDEFI
K 64 ABCFHJ
L 9 ACIJK
M 48 CDFJKL

A 75
B 53 A
C 53
D 14 AC
E 15 BCD
F 97 BC
G 16 BF
H 51 AB
I 46 BDGH
J 39 BDEGH
K 53 ADEFGHIJ
L 3 CEFGI

A 45

AC output:

Code: Select all

Posted: **Fri Jun 28, 2013 12:34 pm**

@brianfry713....for the test case

Code: Select all

A 74
B 55
C 51 A
D 33
E 48 B C D
F 34 B C

Your answer is 159, but...
Critical path for A = A(74) = 74
Critical path for B = B(55) = 55
Critical path for C = A(74) + C(51) = 125
Critical path for D = D(33) = 33
Critical path for E = max(B(55),C(125)) + E(48) = 173
Critical path for F = max(B(55),C(125)) + F(34) = 159
Project completion time = 173(E)

Another test case...

Code: Select all

A 2
B 37
C 16
D 43 A B C
E 20 A B
F 29 A B C
G 36 A D E F

Your answer is 81, but...
Critical path for A = A(2) = 2
Critical path for B = B(37) = 37
Critical path for C = C(16) = 16
Critical path for D = max(A(2),B(37),C(16)) + D(43) = 80
Critical path for E = max(A(2),B(37)) + E(20) = 57
Critical path for F = max(A(2),B(37),C(16)) + F(29) = 66
Critical path for F = max(A(2),D(80),E(57),F(66)) + G(36) =116
Project completion time = 116(G)

Please explain...i think i am not understanding the question...

Posted: **Fri Jun 28, 2013 11:38 pm**

My input was invalid, it shouldn't have had spaces between the letters at the end of a line. I edited it in my previous post.

AKJ88, for this input:

Code: Select all

1

A 2
B 37
C 16
D 43 ABC
E 20 AB
F 29 ABC
G 36 ADEF

Your code at https://ideone.com/1R33VS is printing 81, the correct answer is 116, the critical path is B->D->G.

@ce, your output for the two cases you posted is correct, however now your code doesn't work because there should not be spaces between the letters at the end of a line. Check my updated I/O or post updated code if you're still having trouble.

OJ Board

452 - Project Scheduling

452 - Project Scheduling

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA

Re: 452, Why WA