#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/************************************************************************
Arithmetic Maze

A maze is described by a series of one-way edges. Each edge has an operation
(add, subtract, multiply, or divide) and a value associated with it. Find
the "best" path from the first node to the last. The best path is the one
with the highest value, when travelling along the path and performing the
operations (beginning with 0). If two paths result in the same value, then
the shorter one is preferred. If two paths have the same value and the same
length, then it doesn't matter which one is output.
************************************************************************/

#define MAX 80    /* maximum line length */
#define MSG 6     /* maximum length of points description of any edge */
#define N   50    /* maximum number of nodes */
#define M   100   /* maximum number of edges */

typedef enum { ADD, SUB, MULT, DIV } Operation;

typedef struct
	{
	int from;
	int to;
	Operation op;
	int val;
	} EdgeType;

int read_maze(int *n, int *m, EdgeType edges[M]);
EdgeType parse_edge(char line[MAX], int *n);
void search(int n, int m, EdgeType edges[M]);

/************************************************************************
main
************************************************************************/
void main(void)
{
int n;               /* number of nodes */
int m;               /* number of edges */
EdgeType edges[M];   /* array of edges */
int set = 0;

while (read_maze(&n, &m, edges))
	{
	printf("Maze %d\n", set+1);
	search(n, m, edges);
	printf("\n");
	set ++;
	}
}

/************************************************************************
read_maze

Read a maze. Return 1 if the read was successful.
************************************************************************/
int read_maze(int *n, int *m, EdgeType edges[M])
{
char line[MAX];
int count = 0;

/* Initialize number of nodes and edges to zero. */
*m = *n = 0;

/* Read edge descriptions until the end of file or a blank line. */
while (gets(line) && strlen(line))
	/* Parse an edge description. */
	edges[count++] = parse_edge(line, n);

/* Return 1 iff a maze was successfully read. */
if (count == 0)
	return 0;
*m = count;
return 1;
}

/************************************************************************
parse_edge

Given an edge description, extract the source and destination of the edge,
the operation performed while crossing it, and its value. Also, determine
how many edges there are.
************************************************************************/
EdgeType parse_edge(char line[MAX], int *n)
{
char str[MSG];
EdgeType ret;

/* Read the source and destination nodes. */
sscanf(line, "%d %d %s", &(ret.from), &(ret.to), str);
/* Record the number of nodes. */
if (ret.from >= *n)
	*n = ret.from + 1;
if (ret.to >= *n)
	*n = ret.to + 1;
/* Process the operation. */
switch (str[0])
	{
	case '+' : ret.op = ADD; break;
	case '-' : ret.op = SUB; break;
	case '*' : ret.op = MULT; break;
	case '/' : ret.op = DIV; break;
	default : printf("Unrecognized message '%s'\n", str); exit(1);
	}
/* Process the value. */
ret.val = atoi(str+1);

return ret;
}

/************************************************************************
search

Perform a depth-first search to find the best path from node 0 to node
n-1. The best path is the one with the highest score. If two paths have
the same score, then the shorter path is better.
************************************************************************/
void search(int n, int m, EdgeType edges[M])
{
/* We're really cool, so we'll manage our own stack. None of this so-called
   recursion. */

typedef struct
	{
	int loc;    /* current node number */
	int score;  /* current score */
	int edge;   /* edge used to get to this node */
	int next;   /* next edge to look at */
	} State;

State state[N+1];   /* stack */
int s = 0;          /* length of our stack */
State best[N+1];    /* best path found so far */
int b = -1;         /* length of best path found so far */
int used[M];        /* array indicating which edges have been used */
int e;
int i;

/* Define the initial state. We start at node 0 with a score of 0. We did not
   use any edges to get here. The next edge to look at is edge 0. */
state[0].loc = 0;
state[0].score = 0;
state[0].edge = -1;
state[0].next = 0;

/* Mark all the edges as unused. */
for (i = 0; i < m; i++)
	used[i] = 0;

/* Do the depth-first search. */
while (s >= 0)
	if (state[s].loc == n-1)
		{
		/* We have found a path to the end. */
		if ((b == -1) || (state[s].score > best[b].score) ||
			((state[s].score == best[b].score) && (s < b)) )
			{
			/* This path is the first one, or it's better than the old path,
			   or it's the same score but shorter, then keep it. */
			for (i = 0; i <= s; i++)
				best[i] = state[i];
			b = s;
			}
		/* Pop this state off the stack. */
		if (state[s].edge >= 0)
			used[state[s].edge] = 0;
		s --;
		}
	else if (state[s].next == m)
		{
		/* We have looked at all edges. Pop this state off the stack. */
		if (state[s].edge >= 0)
			used[state[s].edge] = 0;
		s --;
		}
	else
		{
		/* Look at the next edge, and take it if possible. */
		/* Remember which edge we're currently considering. */
		e = state[s].next;
		/* Next time, we will consider the next edge. */
		state[s].next ++;
		/* Make sure this edge starts where we're currently located. */
		if (edges[e].from == state[s].loc)
			/* The next edge does start on our node. Make sure we haven't
			   already used this edge. */
			if (! used[e])
				/* We haven't used this edge yet. Push a new state onto the
				   stack. */
				{
				used[e] = 1;  /* Mark this edge as used. */
				s ++;
				state[s].loc = edges[e].to;
				state[s].score = update(state[s-1].score, edges[e]);
				state[s].edge = e;
				state[s].next = 0;
				}
		}

/* Print out the best path. */
if (b == -1)
	printf("There is no path.\n");
else
	for (i = 0; i <= b; i++)
		printf("%3d: node = %d, score = %d\n", i+1, best[i].loc, best[i].score);
}

/************************************************************************
update

Given a current score and an edge type, return the score obtained by
travelling across that edge.
************************************************************************/
int update(int score, EdgeType edge)
{
int s = score;

switch (edge.op)
	{
	case ADD : s += edge.val; break;
	case SUB : s -= edge.val; break;
	case MULT : s *= edge.val; break;
	case DIV : s /= edge.val; break;
	default : printf("Unrecognized operation\n"); exit(1);
	}
return s;
}