package Ġchapter 4 . section 4 Ċ Ċ import Ġedu . pr inc et on . cs . al gs 4 . In Ċ import Ġedu . pr inc et on . cs . al gs 4 . Queue Ċ import Ġextensions . format Double Ċ import Ġextensions . format Int Ċ Ċ /** Ċ Ġ* Ġ ä¼ĺåħĪ çº§ éĻĲåĪ¶ ä¸ĭçļĦ å¹¶ è¡Į ä»»åĬ¡ è°ĥ åº¦ éĹ®é¢ĺ çļĦ åħ³éĶ® è·¯å¾Ħ æĸ¹æ³ķ Ċ Ġ*/ Ċ class ĠC PM ( private Ġval ĠN : ĠInt ) Ġ{ ĊĠĠĠ Ġprivate Ġval ĠV Ġ= ĠN Ġ* Ġ 2 Ġ+ Ġ 2 ĊĠĠĠ Ġprivate Ġval Ġs Ġ= Ġ 2 Ġ* ĠN Ġ// Ġ èµ· çĤ¹ ĊĠĠĠ Ġprivate Ġval Ġt Ġ= Ġ 2 Ġ* ĠN Ġ+ Ġ 1 Ġ// Ġ ç»Ī çĤ¹ ĊĠĠĠ Ġprivate Ġval Ġdig raph Ġ= ĠEdge Weighted Dig raph ( V ) ĊĠĠĠ Ġprivate Ġvar Ġlp : ĠA cyc lic LP ? Ġ= Ġnull ĊĊĠĠĠ Ġconstructor ( input : ĠIn ) Ġ: Ġthis ( input . readInt ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġinput . readLine () ĊĠĠĠĠĠĠĠ Ġrepeat ( N ) Ġ{ Ġv Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġä½¿çĶ¨ ä¸Ģä¸ª æĪĸ ä¸Ģä¸ª ä»¥ ä¸ĬçļĦ ç©º æł¼ åģļ åĪĨ éļĶ ç¬¦ ï¼Ī æŃ£ åĪĻ åĮ¹éħį ï¼ī ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġinput . readLine (). split ( Regex (" Ġ+ ")) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġweight Ġ= Ġlist [ 0 ]. toDouble () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġæµ ĭ è¯ķ æķ°æį® jobs PC . txt åľ¨ æĿĥ éĩį åĴĮ åĲİ ç»§ ä»»åĬ¡ ä¸ŃéĹ´ è¿ĺ æľīä¸Ģä¸ª æķ´æķ° ï¼Į åĴĮ ä¹¦ ä¸Ń ä¸įåĲĮ ï¼Į å¿½ çķ¥ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsuccess or Ġ= ĠArrayList < Int >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 2 Ġuntil Ġlist . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsuccess or . add ( list [ i ]. toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd Task ( weight , Ġv , Ġ* success or . to IntArray ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsort () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd Task ( weight : ĠDouble , Ġv : ĠInt , Ġvar arg Ġsuccess or : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġdig raph . add Edge ( Direct ed Edge ( v , Ġv Ġ+ ĠN , Ġweight )) ĊĠĠĠĠĠĠĠ Ġdig raph . add Edge ( Direct ed Edge ( s , Ġv , Ġ 0 . 0 )) ĊĠĠĠĠĠĠĠ Ġdig raph . add Edge ( Direct ed Edge ( v Ġ+ ĠN , Ġt , Ġ 0 . 0 )) ĊĠĠĠĠĠĠĠ Ġsuccess or . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdig raph . add Edge ( Direct ed Edge ( v Ġ+ ĠN , Ġit , Ġ 0 . 0 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġsort () Ġ{ ĊĠĠĠĠĠĠĠ Ġlp Ġ= ĠA cyc lic LP ( dig raph , Ġs ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ æľĢ çŁŃ è¿Ĳè¡Į æĹ¶éĹ´ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġtotal (): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġlp ?. dist To ( t ) Ġ?: ĠDouble . NEGATIVE _ INFINITY ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ åħ³éĶ® è·¯å¾Ħ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcritical Path (): ĠIterable < Int >? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( total () Ġ== ĠDouble . NEGATIVE _ INFINITY ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠQueue < Int >() ĊĠĠĠĠĠĠĠ Ġlp !!. path To ( t ) !!. forEach Ġ{ Ġedge Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( edge . from () Ġin Ġ 0 Ġuntil ĠN ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . enqueue ( edge . from ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġqueue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġtotal Ġ= Ġtotal () ĊĠĠĠĠĠĠĠ Ġif Ġ( total Ġ== ĠDouble . NEGATIVE _ INFINITY ) Ġreturn Ġ" Error !" ĊĠĠĠĠĠĠĠ Ġval ĠstringBuilder Ġ= ĠStringBuilder (" Start Ġtimes :\ n ") ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil ĠN ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append ( format Int ( i , Ġ 4 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append (": Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( if Ġ( lp !!. dist To ( i ) Ġ== ĠDouble . NEGATIVE _ INFINITY ) Ġ" Un reachable " Ġelse Ġformat Double ( lp !!. dist To ( i ), Ġ 2 , Ġ 6 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ("\ n ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠstringBuilder . append (" Finish Ġtime :\ n ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( format Double ( total , Ġ 2 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ("\ n ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append (" critical Path : Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( critical Path () !!. join ToString ()) ĊĠĠĠĠĠĠĠ Ġreturn ĠstringBuilder . toString () ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġget Jobs PC () Ġ= ĠC PM ( In ("./ data / jobs PC . txt ")) Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġprintln ( get Jobs PC ()) Ċ }