From e521e49ed4a55c73bf0b069e7cdef2d3ed162885 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Tue, 22 Jan 2013 17:18:14 +0100 Subject: [PATCH 1/1] Initial checkin for move to Git (no prior version history available). --- nodes.txt | 21 ++++++ tsp | Bin 0 -> 32921 bytes tsp.cpp | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 216 insertions(+) create mode 100644 nodes.txt create mode 100755 tsp create mode 100644 tsp.cpp diff --git a/nodes.txt b/nodes.txt new file mode 100644 index 0000000..275dcac --- /dev/null +++ b/nodes.txt @@ -0,0 +1,21 @@ +fg fk 38 +uka lim 19 +lim radion 27 +uka sit 8 +uka ku 9 +sit ku 3 +sit klst 39 +ku klst 38 +klst soci 30 +klst stv 8 +stv laafte 17 +stv ud 8 +laafte ud 15 +ud regi 3 +laafte dg 19 +dg strindens 4 +klst styret 54 +styret ark 15 +ark sangern 13 +sangern fg 13 +uka radion 10 diff --git a/tsp b/tsp new file mode 100755 index 0000000000000000000000000000000000000000..0b22c8b8146cc254ee01d9e60fe09de0d326dad5 GIT binary patch literal 32921 zcmeHwdwf*Ywf~t+2E+3N3pFUnsDma|Xa)ji1ayW>;EYTl5>R|j!X!vEB$!MzC=h58 z%kdD1)>hkVTU!0}daL(`ZPB74B)lT1$U_vc0xFMl9C`SnD&pMl+Gp>XGn1t4{oVWf z?{_}Q*?X_O_S$Q&z4qGAGrO@cI62K`lf;uIT`y6nw7-{u%(ok6^5vpc;nMb%=Ot2(ek?tm>W98%V|I875{%gedPp_$QH3eDKkRi}EkL z^`&#y|E_fY?*F{L|E&z;p>y3XZuZ;fz_)mTM0YK&HgMTXT5AZ)2|MXD4#A{rCoJ@sm z1S5VI2JU^S^;Yj^@OJx51_7d-`ZNR39h~xarXnLeya)JmV5~bjH}n9{?}49Ppx+&x z+#c{tdw|P5Vbep{l+{K;At`j@{h=8ZcURU$DryU=%IfMW>ZApcd9@W~<)Ls{b-1ER3f)!`8SM$p zm=lWBR#b#4tLrL|w5+;3R9i8ptcsB46qiKY`Eiu$n(~U!oU*!#lHAaY5@Z4jmgw?| zaBao>it0%5)FgO388O+=5L!@CTUS$ER#h2U7`i_fRH`4CkEn1%8FB`XH4gwbt)wmw zC0O9j4HbpTE9xS(H46)8Of4x3gbU5+aVS;g-PHuF>zS3FIJvF7s`!3OKBIF(C83J> z3&2xt#RAB&rncug71+0L01(|7J{MvBM`~_vT z6`~Xr5>i9BXh)YZ?gASDT# zXbbAWds!{YL&|`Po?BK~B`v6}td7j(g)ECyG*m{UI_L+1C@t5g`DK;W(v*UN(3nxV zQo-!mzDa?Qd(;?dN-!`9L4fm2e`xfm(WAzail#9OPIlZ5e>(mNVulD}`sq#fKOL@v zy=}1Az0pR5JuSX+A-W!iR0|kAHl#(9VDY(d_pZ4YT~NC8AWsv?c??~KU22Kr+oUUb z9HpB{(`gHNkv%sle70&_-oceR|G+5x) zzImwyPW`rcmRsOdx8iBDz-i1No+mAEs~uf!fm44ko@Xs^>p0{E3tWs1D9t(xoW?ie zX}7>>d?TLMEpRagqPSfaIE|0Qv)=-zv66U{rcX2UH*AumQ_rXGn<`04)0T|Qv9Z_P z?37|7Cg3d(_rgcvd6djJ62miMG=-5+GIp`>k0?y4X0)^LA2ocSJr5wB2~RK+;L!hfbPsfe+Q zh5txlQVpY>g?~?BQVHV)7XB552T^!63qM9-QURllg&(0X4O@++Ec_D+Uqs;r2)j=P z)ZKR}>PJe`(KE#}1D);CEnZ3K?8szJXWKZhq;~@G%eFSEQ$=%B&U8vjOM4_Owu@D1 zoAsHcsK-hOap}ZTWF*y3ebrf7Dk0fz2rA2>SrqCxXIGk{HpR2Q&NWva?w6n(?KVYq zj0I9`&{l?|Ij*84p8d5SZFBqpUK?e1`}WOq=gu7^52q2TB+XKqCdO_;M#wjE;W`2l zZy6i2kD;I-CP#Zi0 zIR?W=nsi&Rb!ZDISfJx*TA@2ur0$#E+V48|N%#A6+k)yTMK#=e1V36YpWPN{ozO@1 zyT0>l7x+ExKDnq}Y1)*oGH3<ZGk1(1#Y?73LX6K(ukFnq4ieYOxP-f<#L9=;Sb zq$2f8_eps;Ddc@fzwtXW-6So~>262rbp0MP^`VW_=6#@9Wcyx!5kNm^q9UP!mikHX zuYN&lKYr|JkPT`MZ3a1m7r~L6X%t?Rv&*-h>{_5hw->gw%PU`}4Ak#~+OXpcdE^N= zh4Pv+ey#sec-`Ay$-GLEz<+pKpf#__-9EQXe)^5ts|(c=zP%@Wy$}0rokii;6m8LK zlHY#4uPGLjn^zN6&wGmpNnr-QR+v|Q$$D)ox^_XfX;jO;C$CQpEcAxE3 zK+8+>sd`cPton_+eTvraFB=D8PVes>)l0vH9EZ(eyg6P)BSU$fhZAw5Eb3`dj#c?E zV`e!nC9d142)@^-sGR@k6DeYQxfofz@*7}mu)(*nH(t6M*|p6od6g2Hre@@1+5_PTEyt@5kz4byz3D@|yEXIHsUx_5I((V%p$86O!t9n#JvF*|X$Q_nx_Joy_QJ z{T~OoX%l48o-VI>%d@-jIP6cSV==%aV|Ca=l$=#=l6_IsDwiI_>uW{*N>T4{9SN%C zt~1~-TWN^})P0fpX02|_2HSco%Aly7in>{8>U2g1!aV3NgFPs%X|ELZ6Gc7bS5Lf5 zO-=95@b@cCj$aj%fz$4A!NgX%GJ{&VD=P?}6HH}qPNZMchl%p3yIZz5Ojoqx%z)aV zwCsrl6?K=QEpP@Q742qS@$6O9-HJT<4aKwli$BOuba>^*wt2HZlQ(Q{*Yf~fr1=IjF| z$wDP(lOQ=zkQ`-}W^UW75~LaQ?3G()!o&;uLm+g;(#)w;3*U+EfW2>}DuIBmhqQv~ zX?;A2RvWx!8YHxym;_LHAsAmo4v?~)SJ9*`= zDM(T~NUG3U?#d*YOk^@Spwncr^P2gXh4!(oxC&<_x)2~856x3$AoPnlKvWz@Lx!a8g2}3Bg z@fbS3fODf+Oj_LdMftCwv`Hw<_rLGk_84 zi+qA=OyBSo6>#DMAn~#{T#9m|^`BBYfyUB~g3(a4u_45h02q#b&1tU2_Tzl_DE zw)(#UHzPj)G^kEIM3JiFFdSnsWH`Mw?}j4J-|xR(>Fk7l#{wJhqG!0#4{z9)pc>Ve zQt6r&p)8RZiU*b}QbHET0DYxtb4E0(tYe9gEa2Jpz+Y&*Z)~9&Q`24gXeOI<7xa>a z|4hlWbQc+~n-NFy`wd`4Ehi%x)Y5DS=tJ>RH=+J-$walTx|p~@{a;5E+Yko=hJ%1w zp`^4nz}}pzcM3UtVtj$z*?7~)2NK2s#$vcy@zGhQPnF&<`NZ3^+A-ja#< zciEULK3?|SqJHDU9}T+Huh_V2*{9D!e_-Y3-3Tqv#_kR{C3U7NUmF}^fMM$Zkk{<+ zwFdi3N_e}{+HbjEyUf@0T`ZENEZah<{pt~mxrAKNhVwlWF9!kNdg@>oy*n3Om4E!m z9{?2DuH+n=OA$)PDSOLVHR8&YSN;_m>r>CV-!D`@#t`B&zq-QpIA9o>1UinVMYBkM zFlr89JOgdZTyi&fUJKrQ^3xyGLdX06mI7>y1?$rX0qFfX#VJkF`nlDhYl3>fxA&;J zTVC@w8@p}&V<=_EJHjTgZYbGOw>fik8c1Xf+!x(D2 z((z%MV(&j1`S{h#jL%tp_+ddN`0ajI{>xNs|9HoxEZ*^>P(*SbiN)TdnSaQtw$z{PN`DBK?C zIFc51ns$$kf!otPAP8QUEP#j}g#>)+c1Y=D?GZ?6A%(e=CLW!_>UQ%9iJ&oMe0oq`4jr&QCaeei}Owab)XS(j-@*KPqNPg(&B6-z)XmF-XUjtBX zE<;$!`MW9C)Ap8_y2#~~S6+)g%BRLiu3v)@9~+hWF@SWxPdauKu%O!P(%}N-OE^rf zF`71re%r6^W;)SHst20Sn@wgc^7W}ZmZYp@GXMGYwn_2eS1*whjMS122SZ z8~mQ#iyn`z;`0^Krv}oeMM9r;f}9`hJ_SA-cbdiD09XWLr(~5Xl~+<>e5lZMq>Mpz zy(@znD>VT1g!`mlecY7}K%u$~3N?te(k4g1mTRunS5S_}tezYJo2lEe$uIz|l;s&zhLPq=Q$%`_vh zo2Y)zXNy{+%b`5PSD}i@w8?Bx+T$_G}JV~3#HU0=~BD(=( zvtmD`)_fHC1U0kDNiRt)wZY^Xy6V>#XUsTiK+5=G02Pw>}Y2>j2 zrlRk{;nlPjY>}3-YJ#1#RFg22KR^``8dcFF(H2ubAQuLMTu25&E>7e|a-l`!#!gcv znSe!JP1e@uU8|8wUU@T<$0rGSOh7`&V=u|WOMb{B2-kg*LFnWN3I22Zoao0 zecQ$4>tXW!#OPA>;QD4H^vxvw2Vg?J zmxBYJ`WDQBsc(HK%*M~?l2llkrsUz z7Qw7@CRtJsk}OjVNS0KCSp+6oVG>p%KQamA8rP#KlUNx|h?PVr#CjhPNUZsQHU5;T z>)0~DSn(R)qKkJBnv(6dI~OO6E5D$1P`Z8+gLl8}2xjUT zp8bnniM|BwqH3c~fhvvULN)3~X{qMS&gO@S&L$7JkYp{<^4JOwJu(5ql>!r&+rFMX|QYUbgtA`CF2P^AXA-ltc zCVft!olhq;NVb z=s6*`v|=Affhti}1Ppk-lUsreIBXNL@@;sQ&|z4b_hJhw2sNQhim`+ld^*9LAFfy2tWZ9>usA9?H(uQnTmEN*2+!= zJO>nYKbDp{u)?Hx+Q0aNSAJp}R(rhJJH7ITvn^*Mt6R=CtTkhU>bqEOU`uuKW9``; z=BnDzpo&S{0lxkuuZr|SiTK)91{%2>^3PmyW?^%cYsZ++)D_c60##n?wyc?_vw6d%Eg@-0~)g!76KcRR@7geUn?CM}X-gwEqYM zNbQ2Gfxh`8vlV4iYm+w0jRH{LRKvPN$bi~}11 z^lS5A2+SsWvB!yApLd-B8Cq1lk!3vA&cIKxK@(P`f@s*ejED8y`W(`o3=<0#D4_lW z7P;1p6pecc!-xQbTDV@rg6m!TDJ#)@|4f<&&Y4XUz#v*L0VQig@5_OVQ-SG5a&+cf z@|{u<^sf1h^hCS&y=u0Y9aLMEb|2S!tN#5f?S8-6?%V%0{p+FKW8FE??t^v|)T)2u z3D8ZumzzIhG0(e>Kzh{Z$r@3?NWG}hr!tqiH*hJldGWGe#C1^pOkVK|kcRMq;1#ooBmvQb6-zSE5~RHtlQ& zmie8KFLW^8*bn~0#{M*n>?#O0BmFyVb4I=*}$^zO|3Z- zxvfZ>29{unPSG9&nIR9^{eRHjS3m$sa+X(-oOq$-)+z*2+j|>CrSCmtY464Q77Fry zIjEi$?R_;+>CwM*fhZctlL*9{(h0IG020AC@NobWbM<+-fmW|>&@n}sog2_HtldNJBJ*X$}2XYLr@Q)|4@AZQ#p<2 z03tom>MZ$SAFJ!OQ+N4@ohNzKJlg3qH?-sxJ3(E2m-4v@U}Gc8Y$O?G~a z6GgFu))l6dMf|k)k0!z?|vIWy8u<|3RA&%eK%!I(hvXJ8_WD zTCP`9^dNS~f}VETb+c^A$&YQy-pvO@ft>cZY1xboFkxEy^8v*gz~;93UZa&b;|5ma z{)A>zenl7~DB3MFP9P-@diDg_R_PA5tJy`poPnG@0ducZUNr^PiU5iWHU1e!g?_U> zehj$LgfO3H(%7gNDsA@ou#$7s< zI6ZKThPO{y1`VNxmrq2Noi{mt4Z=}RQG>V)VB`OgtXTUde%nw6!SBw*Sk%g|u7Y}&Hsf>u1Rjt5YuJ+r(wZYvfOBf?gEi%&bto2wkLVm|6|Tv$V>yc24F*ejfa`}2Amva%UNQ0aL~d%@LA#s9Y< z!ABG>XApCAgFR*a&Hlv7VLcs@G}`)ZKjq2iLTeC7+sscOGLhFGD4s?~EIsg}8{mt+ z9A{ygm4)}IDWeb`VqpWYjqMhBM#fulY3r46uOr;Y2zNOkiJaHOy#`H`;-Tm!FhE?< zJWTf>A#wd7TmrtpS-p%1(wROW8(F5?W?TS|s4a7!->flnKQc`A1RPBOVRH-j+MWlIz2PGKJGOdz+GIfGm>QW znaSDpROGoJZ!8By;L6RkUu?yn#qsGw4SgKp7XXqF;dAk#R9lNO<7+dUaq*&j`);D~ znSvMx9FbaX{v~D1l-?BKxxbqfu8mVz2MT7&!-$I)HoA)Ba)j4b9U&piX6kbhFfM_R zNYRWq)9CkDg%Tc(F%YYt!*s&9jy1{z@JdQQ0>F4?2JI~&ef+#kiGuYP^iDxcJu;b# zhDTjkE1lkHeTL~)QS0Ii(~h~(b$rIAUdK1OXL~VT+82v8eQlRp?#7sv)UWn$C;(d2 zJ>+8KbORBkV+5zMXhf9tT}VPP*Hbn$XpZTx0fgDZ!`EQd=qZ;I5zGd$nZ!YqkgOhY zM7hWrV-Tdpd*VU`krptIq%bN!B{^xgI%zMrZ_JY}RF`9016y(9*WB1IIXb@MpNwt zkjV*7v=AFD3nBjI?LjPMsGEz_U6EnR_+d|8jn&0_$Qq4%$J8-V)SxyS40jfR;UE@D zJbQ}N-9gxRELs%Nv7^+!RBoZoAu3|dyJD=r$^a-n?tO>F8yHNx&B3hx`@x8Yc(bTB zFuGwUi4@Ofxn&L&2qPKdhDI{%9LqUqQ=+x?!Rm;$wSB-85OxDe^w;-7``!SAjXT$} z9B|+X-RxxE&0_UnQ@qcD^exAohABC__$i%LFQWx06Tvyg1XsXsu53IFpD_q88sAd? z>Vj-B<}ig5R1bHR4^`M6)DaLH8!_?vmT0Q)$}7%+43VI76*x--7S}U&X}Cl^tkR01 zlV_7TZ0ezlbp~>F#Yavrflz$Np&{T`w^0Ukb~!HL=HDQcupl&LHZ6$RZ4xdS;fW-F zbej!(P~dw3)Hi%WY&uS4J5fQybaKQQ(+E&y`+ircFLqdMAK%uJl!Q+Egd{*gT!W_;VB+smJltlLURZL{rejKnePvf%0IDn)N*+pgixbXnaPUAdo zk$N7CiSq(TY9J{)hf67N5I36+;%-gXKYZIv_cwkLcN=&)tzXTkebKlM6?hd=V&OZB z9Bjy_2iVpKwk}VrBcBG)vIf2u#IXNEn5v_Z#qGrz(c!RC?meA0D0WO6TLU;dB-)WK zuld6B`J&@ZCvix0Ho$EETpRh~l`ym;rxRX7I+Uy!(~iyvj^S=+hh1r7#5^>>wnw5+BXk<3KKXFeN*lY4B_7rZ zhxSSQIBy8A`>gwZZoyIIT*DhQHc-0z2$>(ng;R zYaEfWlG=g27EDB26k{*|IyA^tnVGJ43zn&Bb<_F*kz3Qk+ld!#-P+#+T}Yz zt1gAu%@Q6(Y$rxZV2>4%%Er!VM1Mx}Gia*2-7-UKI&YJkSE5M=a^8BCgdV^-n!=Wo zOG;l$CkpPEDbQ#ipLz(#zta8c7rv%WTcPLtlF^0o)8EyefacX8Q@{ERbapQa8Ee{U z^F#go>gW2tgR$7;*1TMt&0o|WeHAm;slcTsqF$_xCBHEkxp#Yxx$-SEVwjyrAqZLn zMxXu*W{D2#OA?^X4C}CdFF^4DigD%}gv5Z|pvhbE=L>DVn-$OB1M0iJSpj~0OFb7E z8BpI*)O~DS2B+ovVgZLn5?;!pX>&%PX$y`4eh^fT)gLKRkDFo)s%Lz6Z6-cn23pYb zRb)U={kwh*0ytom5k0B@=}pGJu5wO0;I@?nHLSy(QM8MTw5hCfH3tPn7&mx!6k%-} zw!Vn=6jBBSa?8(9G3aB0@nOf32Wh2=p|f5msUwqH9tM6<&JI4sT{0j2O9rON_@`wa z^evdTVfH4bZpkBzi$-Ozp}anC{V$a&q+`p^z}kO{f>RWkf~@j;BUC%`5-b%^!AZibZA)iZ2$#W z_wj5wqy!*#}?=re&Drn7ab^n76{R8jHsg7 z*(pa(u5X-NbdB{;BP!~Yejg<}l%h{Kv3U+>zQOpE3@fFJK=~D7(L6-?ZGARlX|w2c zBiALy?BlI^!5uSTHuxQO5!LsU5(0$>a=&Eu)(g-h(D%Vtg$mI$OcvK;(_( zci7m+F;=ENCtK0HSv0?LQVdz&*V(oQ0eDOn#bhC7E|0@f~cYJ zW(-!CVB8S%DbELWNijH-+BCrhIPKliam=9BkVPkfn+pIa(rOUE$!1zI_HDpRN}OK{ zXm?_f`2EPOMJ;FR`x_s@5SZ(hY7|R~*fKhy_hxEAt0?!H$DYl~lv_GMNzooc88LBP(LtkNA3Zw5hOy% zBwhfkh)54^#BT6ogC_ ztpOsKoy^3~nFv^4uJtMgTlE zSqJHC3en2aot##d;RUUDq5X++G~%=$b!>PQw3-!f>I3cOBUQU#I zuceQWSDDi$YPM4-)qPa=iG%U-s;OKzrt4QRs#e`Fo}@^W&)IG1g%l~)T6$B8PW{R) zrWBpVHJD=(9q3FqQXI-;WyV_R$SntWOU~90ZZ>IU8{06L>RF0jy%f3r3sUsy*AimS zQjF)3q@LMaT$A*#!I3cpL4nw{QGdwQvp|1?koP33r$`q`YSjICEnlxcL216XWDrSe z)H^sQH|W)b_$q=49q74Hvkuw(5buFZJxmLG7)Y`q<4d5^eSfVa_19at)}uC4`s+nJ z1{z_;#QW=edEeW$zrKRUbnUPIlj{X6d{TdXH-lUH>$jmMW*5zS?Z|`X`kd&ey=Fh{ z1$(Le^gxm~b;rs5bp2d1TIC&xM0bpX9*dn_y5lBfOFi%P4D0=f13hna1@*37y4~|& znR?hCa8xJtu=Mqk#R{w>D{zCp8Yt19@V*mlCH0;4<5(B@W;?Y8bdjH+)~VOA^k~?W zjH}R0&@ygCFs^G?STbBo8BWlDOc_3#&>c&Uc90q^#E<5k!p9^sZW($3V}v@`DWs0T zMm2WD2G?X(2XpL9BZj6B=jnP2PtOuhUeMH=M2A<8 zF9;9o*HAvx*=?b0(AigMkqxhL<5vWXsk6Z`hsbA_&aW&>Ztn__UVUU#YCX*clXmL zyGIoDE&7fZ)5beoyD+^7Vq$S7h}Dd*K_g#jIg5{Z<>p1qK%iEojrn-#>%lUgg``Kr` z>;vD#x4l6PlN&m$mYU5xtF@XrG4QwSgdO^zJl;A^JRI( zApr34>K{$JX}rzjwfYR2iLh^cyPl2knFkDg**gnyz_1W=p`n(~a(@v&NI=_kKCEtZ zoEmOC1V1bxeYgCJ^`x?=^#LSyw3@T8Vlj6h18$AtQ_`*aQI0Vb7*++r7jF1)o6mBc zL2Y^_+tsLqeGh8ANU~8kTQ|W5L40B2AMJ-MhgKA^{g7?u_QGMdPfryRKh~F0A=dp6 z+KwbhR9aHk~c&e&_vA7d@l};4`<2ES*+tYq5lZ73F7NV zb_nU8?1Q8*Dz|K7`9OQ(Ck$8qk%6qc11YJjn*;KySAm|`&0$L?&jRG$W2}JFrZ7EO z2&FgA(BOnaF!|GMul0LyXCP-2UjUL<(L9q2MqUv{fG^E_46jjwS3*x0^~ahG?Q_Yh z7lI0^AK`3*`z-0sComMRPy=5+)0Kr&AsBdUanj@k&Ce^Dn;46+dTDN8V0jAr7nVh) zjwJq2af!VPnq`SoAFb@DM8m`GJ<%tEt#@Y_w}3w=CN@Me$O6F}u^$$|ZwZ*cF3|Mp zJjJt(eTDx8mh%d4Ivkh$n3xBh|xo;$N53rHf%*I{U&4aKTPv6EKytXb{GmLan0=y6r= z3L3~!R@*@x0>H_RO9>>hvQwa`fmULUP>IwJ*?}~+KpDbd-&l>hNUWF8ag8~w#%QOG zwHDeve5?Z&q{ElJ9p+;@R>|>gV|^8PN+@b$8P9U@Oq9$iH~*0_c36J|rNctK6MLyJ zA^1vL&yS+%w9CzxAZMlNA!2Q@$r}4Y96#uCTHk`Q7!Dwab2Hl;W?{*jhByx~4rLyK|_a^I6oMU@Ji6W@7V$%e=3etbI`|K3t*YQ#cY z3zggynEnczk=@}^r~@mezH2u9E=4Jt&AiQE7kpxSaXD*#UWtmM`cVWfH=~9{;B=M01-{w;QB1SdTe|0x8-o=+lQ}P)_T=#GwS^ATK}D?@eaJQi|v> z%OCIILZEK0DE|a8ZN_wjVYke7VWv|kol3E7ZC}u@kyyU(wv1<5M;^{_;{3sg{p6VD zBtE2}K@N>;f;q>0>iK|*Pi@cJ1NdA$ycXKa`tdbRY|!7ZdTdiX z(b`YC`yG;$u?p{G2JRXUTDk)9pVrD?%jy;>zpI%`bZVY@&0dTN+X4ynRIZ zo%C`>YMgjeWF0(rA`x8jN^|dKSUBEceeSQREO*W+3*Q^5#VZ>>3wVtauN=a$U1A^K z4)-Gb9|dbi;XeLSEJmvik-x@bbYv?J)?^FZ=9go!@8Ax41@SN*U&4JJ?okZ=KZW}Y zHc#@fzU(>_i_w|cXYf(U3gEj=K-mzVr^jM^PN7`;gYvQ0An0p4juNf0M2E1yBe=mm^XyWmvtnRyId z3h>jb?(`Dv$t%-9zM$0(j(seLf~H;%JLuRldnjExN;(hxOs5ie71SGeLX3T!%<5UxMEkPR3#v z!=IjhmzQ*i=+PnHb%57VCH_NtOOxnPJCZ)<^fFC)q}$Z4G61Li(uV?Gw8HUluiFQB zC$CCdX>Yoq75Na}HE2gi@B>2wA8S<7IGV#^^(~lD?*= zbPmOuj^s#>?LpRRY@)pooOs=Z;R6*%JXB7~>vh0Y0^UTj2tgK27mzea7UGH7huHdE z?U-&4W!6X!La89X#XK@*A7RTH1=u9Vi#GdRH%ii0n`4Jf+Gk6}yU8~BQpX#8r1mt& z*1pn7yW@$z(mUynm-|ZJr8_qCmA-Tkq@$PPd~fN4UXB+tZ0CE8_@cLMPln^G4C&{+ zLGRbSFM=1jn-5x2Muy`;X)vOa{PrB%up0op*>Tuz4?8y6?TZjPXm=d7OQ-GdCJKOb z;W4CW=h7UVmr8AR$C}Hf-`gFnmrKv~c6@oM^w-{w!%zUT>4!fg1p+t@!h4; z8+{zxhDrPTIMxo6PWBn}({Ja}gVVL_S=ZOgT%2fT&;DDy%oWY0G|dcSd8CFSoOUxDuisu~SoEI?j~By{ zU-SIP^wN`MI`Q9i=Ry3!ulZ!mDPOriy9dW1a?cAds9^fdJLGFQMA9)_u5PcC<% zlVj;E*#53qH>9@Nam$nfm|zTij=mn$vM!PiMK?tDl#l{E)j>a(5he zCv*2^?#|`z{oH++yT9P>AGrGxceio(UG5&|?pf~k>d*7%?v>mf$KA=?y_vhI<-xB{ zU+2vBSIns_t9Is%${RIyWPXn6pjdSOUNNH5v!ugT1IdCJjraMpgFu<*-T_BCB zu8CBP!jD>yjFjEYLw8r#kD60oiTf2Q%cW5inpajgPa0Leup0DCH&ScH+>akLudJy~ z3WN|>TTxX;3Ak@TRYV$9S&g6A9)(}p#(ORTh^r|ti~1b$&31RXzM82Z$R^uo?Lxk1S8 zAw366)8HW+C(;W$sPOdbcm$P^WGC_$_ULB72vww)dU+AT!wsvjqb4w6&qeqyc*ur{ z^uliahG%pgM-+Bi;0gC$#FI@FVPO~d^YjaNdg7n>6#R3r^dLMWOOamKVTBuBVTVQj zBE2Yob4q$)*Bf|xFDFdtsjo^+zY;K#tDrCXwRKb}ctk#C$mCV{$yM=hO}~rV*rL{>)fO zYKO;~o~FU{RNcuOiI(uJPYO9{4FJlb>B%ykcs(;9 zUa9Gi0A|gfewLe_Y}4t2pPK#{a7lLs|6&}F%hT`T<)`*Xk4P`-@f2Xz{G~aigeFOI zOh@3Gp+tHC{{j)#^kN*A!PD;-3AroM3HQ5{^hbF9M|gU{rywKJi7@?gE5SthrEn>W zI>XbSVWGs!neZ~-1xQc)=cd3#dQS?RaOn{)rnHH?S&aG037al`L1%qZf{ad@6@mM` zRi-DK+mYc2j={euztBrEbMdm9N!WYd17^U@?VyNC&0oN~bM3@knzu_7-PemiDU!d_V;?YPBD*r8a#S)mNZzvoa%?4BC@FNEADu;Xq z?<$8vz$xDsQu4i>;a?&-!=>;g?880Ge~FYGE`=}AejDH?I!?a6$|CXViT`HA5&xMf z{6EUz7fSPZzbEMYmchI7{~X|y?`q!93;Ygvx|7>>jxW|1cJl=9!?mGzqaUiLX9#-( zhKeEjOE2^?$UzQgb~df6J`7_O*|lCq^#Jz)ZcFQ`hxFZ!vm3pd1^DIQ$2-mBht@pl zp?>i~)0^}@%HS9^arp?_OzFDA9}NVef5zu!bl93Ne7^(yLcqm%PGs^d;7$>+xPR>d z{syCCLFC>;J-|Qj0p8zEx^;+%p1H6vytQft_S?~9^mJDfM1G%UU&7C-vfLG-~*x0!VV+I zp0XbB8+w3ifM<52hfnr^zlFgehY?f7zI_~CJj8^vJqW-L1J3lh*o3pSdB6)X ziKY70!=(r%<|#J;-kls)ar~p3oO-L*oGp#L0)ujX*J$AWkph8l$5#`Tl!RRMk#;N9gr8F0#Xb+{B*iSgtN zz?}?|{3>H~V23lkEQ0OD!M6Z#R^D(agNs)^;KWa<&&xoM@Q6n^og;kxcO!>C#qoE| zF!9;m4C1apL++0M8vyU_e!*(Msa(6lrAVFVzv_CR^C;lNCtbut&!5;^lAZ^=yL$W! zr;~c$;X4eD^8UcfD9|1rJ*POn8A`lu80U6Zt|1H#`#jLgkehjuD>^!nh-^VCM80p92 zA+~B4Dywh6&i(uaRTYtn@=@c)O*Wv_P=|tC8x$OLZrJZ|JMqakJ~RRYH{UeAzj5eCh00pR(wf_)S{z3-2aJ- zHp}Lx@=DiWrogN>L?#Q$RGd&vBhD7le{JekW&243mj@rDh68f$6BTa@;3c zUsr)9Lsy;BouA3+*)5zY2}3DOsOK9}lWCzA-1E!stq9F8i_}&&(CwmQU=}JXEB}{U z;y7q4Z;7bL`|8=Xrf783s_Nz;`?`CPW0K_m>Gi3}MVW(}U_*4O$&_2t4XMePp-_2U zO=uqOv&EJPx6Q&%GL50;PRb_5%^}+D80a?HAz^1=k4&{QZ)FW(D@8Q8|LOI)$?US0 z6sm*Tn{_f~e%XR#!&n(-iW|SUp)4$n-x+H)Jg}xE5l<*kj%^>@wM(rhP9k2ee{5jt zZ~-p00U-{np)L$p(OtCeP)QzL1q>~=-pHF=x;or(TUQY($9=?IuOYT}LXz2ykO{T) z3A}jj(d@ojiyHqgT3YwDsme>;&FF;54cAmd_bRbtScaaO8DFzYG0k86X5SP8C@wPY z;ez30IWYlsxpKG*#mKn((J2xWbxG=3!S?&QyJb0rgxdqV9lke&4nf@fTv1+(5e?nN eoXk@4jlziI*8qoZ%V(WG49WcxyCB$XP5%Xbe*eh; literal 0 HcmV?d00001 diff --git a/tsp.cpp b/tsp.cpp new file mode 100644 index 0000000..2c64c59 --- /dev/null +++ b/tsp.cpp @@ -0,0 +1,195 @@ +#include +#include +#include + +#include +#include +#include +#include +#include + +using namespace std; + +#define INFINITY 10000 + +vector places; +set places_set; +map, int> sparse_dist; + +int* dist; + +void check_name_inserted(char* name) +{ + if (places_set.count(name) == 0) { + places_set.insert(name); + places.push_back(name); + } +} + +void make_matrix() +{ + int num_places = places.size(); + dist = new int[num_places * num_places]; + + for (int i = 0; i < num_places; ++i) { + dist[i * num_places + i] = 0; + } + + for (int i = 0; i < num_places; ++i) { + for (int j = i + 1; j < num_places; ++j) { + int d = INFINITY; + + pair comb = make_pair(places[i], places[j]); + if (sparse_dist.count(comb) != 0) { + d = sparse_dist[comb]; + } + comb = make_pair(places[j], places[i]); + if (sparse_dist.count(comb) != 0) { + d = sparse_dist[comb]; + } + dist[i * num_places + j] = d; + dist[j * num_places + i] = d; + } + } +} + +void print_matrix() +{ + int num_places = places.size(); + for (int i = 0; i < num_places; ++i) { + printf("%d: %s\n", i, places[i].c_str()); + } + for (int i = 0; i < num_places; ++i) { + for (int j = 0; j < num_places; ++j) { + printf("%5d ", dist[i * num_places + j]); + } + printf("\n"); + } +} + +void floyd_warshall() +{ + int num_places = places.size(); + + for (int k = 0; k < num_places; ++k) { + for (int i = 0; i < num_places; ++i) { + for (int j = 0; j < num_places; ++j) { + dist[i * num_places + j] = + min(dist[i * num_places + j], + dist[i * num_places + k] + dist[k * num_places + j]); + } + } + } +} + +int *cache; +int cache_size; +int best_cost; +int finish_mask; + +void init_tsp() +{ + int num_places = places.size(); + cache_size = (1 << num_places); + cache = new int[cache_size * num_places]; + + for (int i = 0; i < cache_size * num_places; ++i) { + cache[i] = -1; + } + + best_cost = INFINITY; + finish_mask = (1 << num_places) - 1; +} + +int tsp(int node_num, int visited_mask, int cost_so_far) +{ + int num_places = places.size(); + if (cache[node_num * cache_size + visited_mask] != -1) { + return cache[node_num * cache_size + visited_mask]; + } + if (cost_so_far > best_cost) { + return INFINITY; + } + + if (visited_mask == finish_mask) { + return 0; +/* + cost_so_far += dist[node_num * num_places + 0]; + cache[node_num * cache_size + visited_mask] = dist[node_num * num_places + 0]; + if (cost_so_far < best_cost) { + best_cost = cost_so_far; + } + return dist[node_num * num_places + 0]; */ + } + + int best_this_cost = INFINITY; + for (int i = 0; i < num_places; ++i) { + if (visited_mask & (1 << i)) { + continue; + } + + int cost = dist[node_num * num_places + i] + + tsp(i, visited_mask | (1 << i), cost_so_far + dist[node_num * num_places + i]); + if (cost < best_this_cost) { + best_this_cost = cost; + } + } + + cache[node_num * cache_size + visited_mask] = best_this_cost; + return best_this_cost; +} + +void backtrack(int node_num, int visited_mask) +{ + int num_places = places.size(); + if (visited_mask == finish_mask) { + return; + } + + int best_node = 0; + int best_this_cost = INFINITY; + for (int i = 0; i < num_places; ++i) { + if (visited_mask & (1 << i)) { + continue; + } + + int cost = dist[node_num * num_places + i] + + cache[i * cache_size + (visited_mask | (1 << i))]; + assert(cost != -1); + if (cost < best_this_cost) { + best_node = i; + best_this_cost = cost; + } + } + + printf("%s [%d] [%d to %d costs %d]\n", places[best_node].c_str(), best_this_cost, node_num, best_node, dist[node_num * num_places + best_node]); + backtrack(best_node, visited_mask | (1 << best_node)); +} + +int main(void) +{ + for ( ;; ) { + char name1[256]; + char name2[256]; + int dist; + + if (scanf("%s %s %d", name1, name2, &dist) != 3) { + break; + } + + check_name_inserted(name1); + check_name_inserted(name2); + sparse_dist.insert(make_pair(make_pair(name1, name2), dist)); + } + + make_matrix(); + print_matrix(); + printf("\n"); + floyd_warshall(); + print_matrix(); + + init_tsp(); + tsp(0, 1, 0); + printf("fg [%d]\n", best_cost); + backtrack(0, 1); +} -- 2.39.2