The Final Stand - Defeat the Zombie Horde Introduction

You are alone on an island. The remainder of humanity is dead (probably due to the bug in user12345's code). The Zombie Pirate Horde has reached your island, and they are endless. It's time to kick ass or chew bubble gum, and you're all outta bubble gum.

Problem

Our doomsday scenario is described by 2 integers on a single line, m and n. On your island are outposts uniquely numbered from 1 to m. The following n lines each contain three integers, x, y, and z, separated by a space. x and y are the unique IDs of two outposts, and z is the number of zombies that will be encountered on the path between them.

When you travel a path, you lose z ammunition and you kill z zombies. If you travel the same path again, you will encounter the same number of zombies, unfortunately. All outposts generate +1 ammunition each time you travel a path. You begin with 100 ammunition at outpost 1. All outposts begin with 0 ammunition. You die immediately if no path exists for which your ammunition is greater than the number of zombies on that path, and the remainder of your ammunition is converted to kills. Such is your final stand.

Write a program that outputs the maximum number of zombies you can kill for a given scenario. If you can kill an infinite number of zombies, simply output x.

Example Input

5 6
1 2 4
2 3 4
3 1 4
2 4 10
2 5 10
1 1 50


Example Output

x


Assumptions


A path will be between two valid outposts. That is to say 1 &lt;= x/y &lt;= m
If a path between x and y is not listed, it cannot be traveled
A path is bidirectional
1 &lt; m &lt;= 100
1 &lt; n &lt;= 500
Input must be provided through stdin, read from a file, or accepted as a sole argument to the program, and it must exactly follow the format of the example
The runtime of your program may be arbitrarily large but must be determinably finite


The code with the fewest characters wins!
Java ( less grotesque: 8415 5291 3301)
Ok. Basically, I'm embarrassed no-one has submitted a solution. So a few days ago I began trying to solve this problem, b/c it's great.. Follow that link to watch my progress on it via GitHub.
Edit
New solver version, much more &quot;golfed&quot;, with corrected cycle checker as identified by MT0. It also supports fast-forwarding routes, tuneable by changing how much memory is available to the VM. Latest BIG edit: realized that I had a few other small index errors and premature optimizations, that resulted in a failure to consider quite a large number of types of wins. So that's fixed, carefully. The new version is both smaller and below.
For our reference route, java -Xmx2GB ZombieHordeMin does the trick quite nicely (be warned, it will take a while).
Cool factoid
In a fascinating twist, there are MANY solutions at length 24, and my solver finds one different from MT0's, but identical in principle, except that it starts by visiting the the other outposts connected to 1. Fascinating! Totally counter human intuition, but perfectly valid.
Solution Highlights
So here's mine. It's (partially) golfed, b/c it's an exponential, almost-brute-force solver. I use an IDDFS (iterative deepening depth first search) algorithm, so it's a great general solver that doesn't skip, so it solves both parts of the OP's question, namely:

If a winning route is found (infinite zombies), output 'x'.
If all routes end in death (finite zombies), output the largest number of zombies killed.

Give it enough power, memory, and time, and it will do just that, even slow-death maps. I spent some more time improving this solver, and while more can be done, it's a bit better now. I also integrated MT0's advice on the best infinite-zombies solution, and removed several premature optimizations from my win-checker that prevented the previous version from finding it, and now I do in fact find a very similar solution to the one MT0 described.
A few other highlights:

As mentioned, uses an IDDFS to find the shortest possible winning route.
Since it is at core a DFS, it will also discover if every route ends in the death of our hero, and keeps track of the &quot;best&quot; route in terms of most zombies killed. Die a hero!
I've instrumented the algorithm to make it more interesting to watch Removed for golfing purposes. Follow one of the links to github to see the ungolfed version.
There are a number of comments throughout as well, so feel free to re-implement for your own solution building on my approach, or show me how it should be done!
Memory-adaptive route fast-forwarding

Up to available system memory, will keep track of &quot;end routes&quot; that did not result in death.
Using a fancy route compression and decompression routine, progress from a prior iteration of IDDFS is restored to prevent rediscovery all prior visited routes.
As an intentional side-bonus, acts as a dead-end route cull. Dead end routes aren't stored, and will never be visited again in future depths of IDDFS.



History of the solver

I tried a bunch of one-step look-ahead algorithms, and while for very simple scenarios they would work, ultimately they fall flat.
Then I tried a two-step look-ahead algorithm, which was.. unsatisfying.
I then began building an n-step lookahead, when I recognized that this approach is reducible to DFS, yet DFS is far ... more elegant.
While building the DFS, it occurred to me that IDDFS would ensure (a) find best HERO (death) route or (b) first winning cycle.
Turns out building a win-cycle checker is easy, but I had to go through several very very wrong iterations before I got to a provably successful checker.
Factored in MT0's win-path to remove three lines of premature optimization that made my algorithm blind to it.
Added an adaptive route-caching algorithm that will use all the memory you give it to prevent unnecessary redoing of work between IDDFS calls, and also culls dead-end routes up to the limits of memory.

The (golfed) code
On to the code (get the ungolfed version here or here):
import java.util.*;public class ZombieHordeMin{int a=100,b,m,n,i,j,z,y,D=0,R,Z,N;int p[][][];Scanner in;Runtime rt;int[][]r;int pp;int dd;int[][]bdr;int ww;int[][]bwr;int[][]faf;int ff;boolean ffOn;public static void main(String[]a){(new ZombieHordeMin()).pR();}ZombieHordeMin(){in=new Scanner(System.in);rt=Runtime.getRuntime();m=in.nextInt();N=in.nextInt();p=new int[m+1][m+1][N+1];int[]o=new int[m+1];for(b=0;b&lt;N;b++){i=in.nextInt();j=in.nextInt();z=in.nextInt();o[i]++;o[j]++;D=(o[i]&gt;D?o[i]:D);p[i][j][++p[i][j][0]]=z;if(i!=j)p[j][i][++p[j][i][0]]=z;D=(o[j]&gt;D?o[j]:D);}m++;}void pR(){r=new int[5000][m+3];r[0][0]=a;Arrays.fill(r[0],1,m,1);r[0][m]=1;r[0][m+1]=0;r[0][m+2]=0;ww=-1;pp=dd=0;pR(5000);}void pR(int aMD){faf=new int[D][];ff=0;ffOn=true;for(int mD=1;mD&lt;=aMD;mD++){System.out.printf(&quot;Checking len %d\n&quot;,mD);int k=ffR(0,mD);if(ww&gt;-1){System.out.printf(&quot;%d x\n&quot;,ww+1);for(int win=0;win&lt;=ww;win++)System.out.printf(&quot; %d:%d,%d-%d&quot;,win,bwr[win][0],bwr[win][1],bwr[win][2]);System.out.println();break;}if(k&gt;0){System.out.printf(&quot;dead max %d kills, %d steps\n&quot;,pp,dd+1);for(int die=0;die&lt;=dd;die++)System.out.printf(&quot; %d:%d,%d-%d&quot;,die,bdr[die][0],bdr[die][1],bdr[die][2]);System.out.println();break;}}}int ffR(int dP,int mD){if(ff==0)return pR(dP,mD);int kk=0;int fm=ff;if(ffOn&amp;&amp;D*fm&gt;rt.maxMemory()/(faf[0][0]*8+12))ffOn=false;int[][]fmv=faf;if(ffOn){faf=new int[D*fm][];ff=0;}for(int df=0;df&lt;fm;df++){dS(fmv[df]);kk+=pR(fmv[df][0],mD);}fmv=null;rt.gc();return kk==fm?1:0;}int pR(int dP,int mD){if(dP==mD)return 0;int rT=0;int dC=0;int src=r[dP][m];int sa=r[dP][0];for(int dt=1;dt&lt;m;dt++){for(int rut=1;rut&lt;=p[src][dt][0];rut++){rT++;r[dP+1][0]=sa-p[src][dt][rut]+r[dP][dt];for(int cp=1;cp&lt;m;cp++)r[dP+1][cp]=(dt==cp?1:r[dP][cp]+1);r[dP+1][m]=dt;r[dP+1][m+1]=rut;r[dP+1][m+2]=r[dP][m+2]+p[src][dt][rut];if(sa-p[src][dt][rut]&lt;1){dC++;if(pp&lt;r[dP][m+2]+sa){pp=r[dP][m+2]+sa;dd=dP+1;bdr=new int[dP+2][3];for(int cp=0;cp&lt;=dP+1;cp++){bdr[cp][0]=r[cp][m];bdr[cp][1]=r[cp][m+1];bdr[cp][2]=r[cp][0];}}}else{for(int chk=0;chk&lt;=dP;chk++){if(r[chk][m]==dt){int fR=chk+1;for(int cM=0;cM&lt;m+3;cM++)r[dP+2][cM]=r[dP+1][cM];for(;fR&lt;=dP+1;fR++){r[dP+2][0]=r[dP+2][0]-p[r[dP+2][m]][r[fR][m]][r[fR][m+1]]+r[dP+2][r[fR][m]];for(int cp=1;cp&lt;m;cp++)r[dP+2][cp]=(r[fR][m]==cp?1:r[dP+2][cp]+1);r[dP+2][m+2]=r[dP+2][m+2]+p[r[dP+2][m]][r[fR][m]][r[fR][m+1]];r[dP+2][m]=r[fR][m];r[dP+2][m+1]=r[fR][m+1];}if(fR==dP+2&amp;&amp;r[dP+2][0]&gt;=r[dP+1][0]){ww=dP+1;bwr=new int[dP+2][3];for(int cp=0;cp&lt;dP+2;cp++){bwr[cp][0]=r[cp][m];bwr[cp][1]=r[cp][m+1];bwr[cp][2]=r[cp][0];}return 0;}}}dC+=pR(dP+1,mD);if(ww&gt;-1)return 0;}for(int cp=0;cp&lt;m+3;cp++)r[dP+1][cp]=0;}}if(rT==dC)return 1;else{if(ffOn&amp;&amp;dP==mD-1)faf[ff++]=cP(dP);return 0;}}int[]cP(int dP){int[]cmp=new int[dP*2+3];cmp[0]=dP;cmp[dP*2+1]=r[dP][0];cmp[dP*2+2]=r[dP][m+2];for(int zip=1;zip&lt;=dP;zip++){cmp[zip]=r[zip][m];cmp[dP+zip]=r[zip][m+1];}return cmp;}void dS(int[]cmp){int[]lv=new int[m];int dP=cmp[0];r[dP][0]=cmp[dP*2+1];r[dP][m+2]=cmp[dP*2+2];r[0][0]=100;r[0][m]=1;for(int dp=1;dp&lt;=dP;dp++){r[dp][m]=cmp[dp];r[dp][m+1]=cmp[dP+dp];r[dp-1][cmp[dp]]=dp-lv[cmp[dp]];r[dp][m+2]=r[dp-1][m+2]+p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];r[dp][0]=r[dp-1][0]+r[dp-1][cmp[dp]]-p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];lv[cmp[dp]]=dp;}for(int am=1;am&lt;m;am++)r[dP][am]=(am==cmp[dP]?1:dP-lv[am]+1);}}

Get the code from github here, to track any changes I make. Here are some other maps I used.
Output example
Example output for reference solution:
    $ java -d64 -Xmx3G ZombieHordeMin &gt; reference_route_corrected_min.out
    5 6 1 2 4 2 3 4 3 1 4 2 4 10 2 5 10 1 1 50
    Checking len 1
    Checking len 2
    Checking len 3
    Checking len 4
    Checking len 5
    Checking len 6
    Checking len 7
    Checking len 8
    Checking len 9
    Checking len 10
    Checking len 11
    Checking len 12
    Checking len 13
    Checking len 14
    Checking len 15
    Checking len 16
    Checking len 17
    Checking len 18
    Checking len 19
    Checking len 20
    Checking len 21
    Checking len 22
    Checking len 23
    Checking len 24
    25 x
     0:1,0-100 1:3,1-97 2:1,1-95 3:2,1-94 4:5,1-88 5:2,1-80 6:4,1-76 7:2,1-68 8:1,1-70 9:2,1-68 10:1,1-66 11:2,1-64 12:1,1-62 13:2,1-60 14:1,1-58 15:2,1-56 16:1,1-54 17:2,1-52 18:1,1-50 19:2,1-48 20:1,1-46 21:2,1-44 22:1,1-42 23:2,1-40 24:1,1-38

Read the route output like this: step:source,route-to-get-here-ammo. So in the above solution, you would read it as:

At step 0, at outpost 1 with ammo 100.
At step 1, use route 1 to get to outpost 3 with ending ammo 97
At step 2, use route 1 to get to outpost 1 with ending ammo 95
...

Closing notes
So, I hope I've made my solution harder to beat, but PLEASE TRY! Use it against me, add in some parallel processing, better graph theory, etc. A couple of things I figure could improve this approach:

aggressively &quot;reduce&quot; loops to cut out needless retread as the algorithm progresses.

An example: in the example problem, consider the loops 1-2-3 and other permutations as &quot;one step&quot;, so that we can make our way to end-cycle more quickly.
E.g. if you are at node 1, you can either (a) go to 2, (b) go to 1, (c) go through 1-2-3 as one step and so on. This would allow a solved to fold depth into breadth, increasing the number of routes at a particular depth but greatly speeding time-to-solution for long cycles.


cull dead routes. My current solution doesn't &quot;remember&quot; that a particular route is dead-ended, and has to rediscover it every time. It would be better to keep track of the earliest moment in a route that death is certain, and never progress beyond it. did this...
if careful, you could apply the dead route culling as a sub-route cull. By example, if 1-2-3-4 always results in death, and the solver is about to test the route 1-3-1-2-3-4, it should immediately stop descending that path as it is guaranteed to end in disappointment. It would still be possible to calculate # of kills, with some careful math.
Any other solution that trades memory for time, or allows aggressive avoidance of following dead-end routes. did this too!