\documentclass[11pt]{article}

\marginparwidth 0pt
\oddsidemargin -0.4in %0pt
\marginparsep 0pt
\topmargin  -0.6in
\textwidth  7.2in%6.5in
\textheight  9.1in

\parskip 1.3ex
\parindent 0ex

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[xdvi,dvips]{graphics}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{dsfont}
\usepackage{xspace}
%\usepackage{figlatex}

\graphicspath{{Figures/}{./}}

\input{preamble}
%\input{special}

\newcounter{jump}
%\newcounter{jumpaction}
%\newcounter{jumpfunction}

\newcounter{tbl}
\newcounter{fgr}
\newcounter{prp}
\newcounter{action}
\newcounter{priority}

%\renewcommand{\linecomment}[1]{}
%\renewcommand{\datecomment}[1]{}
%\renewcommand{\bfcomment}[1]{{}}

\newcommand{\back}{\mbox{\it back\,}}

\renewcommand{\Label}{\label}
\renewcommand{\Ref}{\ref}
\renewcommand{\Refstepcounter}{\refstepcounter}

\renewcommand{\today}{}

\raggedbottom


\title{More on HW7: The Two Traveling Salesmen Problem}


\begin{document}

\maketitle

\section*{Hints:}
\vskip 5in
\eject

{\bf\Large Examples:}\\
Let $G$ have $n$ vertices, named $1,2,\ldots n$, in topological order.
Thus, there is no edge $(i,j)$ if $i\ge j$.

{\bf Example 1:}
Let $n=20$, and let $G$ be a complete acyclic directed graph, {\ie}
there is an edge from $i$ to $j$ if and only if $i < j$.
Let the weights $\braced{W(i,j)}$ be given by the following table;
for example, $W(1,2)=5$. A blank entry means that $W(i,j)$ is undefined,
or $\infty$ if you prefer.
\vskip 0.05in

{
\footnotesize
$\begin{array}{|c||c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|c| c|c|c|c|}
\hline
  &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\ \hline \hline
 1& &5&6&7&8&6&8&5&8&4&6&6&4&4&3&9&1&9&3&4 \\ \hline
 2& & &5&8&8&5&5&6&4&9&8&1&4&1&6&1&4&8&9&8 \\ \hline
 3& & & &2&8&8&9&5&8&8&5&5&8&7&2&7&6&6&2&5 \\ \hline
 4& & & & &9&7&5&1&4&5&3&2&7&7&5&2&6&2&1&3 \\ \hline
 5& & & & & &6&2&6&3&6&4&9&9&7&5&4&6&4&9&7 \\ \hline
 6& & & & & & &1&1&9&7&6&7&2&2&4&2&7&3&6&4 \\ \hline
 7& & & & & & & &3&6&1&4&6&9&9&1&6&2&6&2&9 \\ \hline
 8& & & & & & & & &6&6&3&4&5&5&3&6&2&4&1&7 \\ \hline
 9& & & & & & & & & &6&3&2&8&2&9&4&6&8&1&1 \\ \hline
10& & & & & & & & & & &6&8&7&1&9&9&8&5&5&9 \\ \hline
11& & & & & & & & & & & &1&6&5&7&1&1&4&3&9 \\ \hline
12& & & & & & & & & & & & &2&4&3&5&2&7&3&8 \\ \hline
13& & & & & & & & & & & & & &4&9&1&2&7&6&6 \\ \hline
14& & & & & & & & & & & & & & &8&3&5&5&9&1 \\ \hline
15& & & & & & & & & & & & & & & &9&6&1&9&3 \\ \hline
16& & & & & & & & & & & & & & & & &3&1&7&8 \\ \hline
17& & & & & & & & & & & & & & & & & &2&6&7 \\ \hline
18& & & & & & & & & & & & & & & & & & &8&3 \\ \hline
19& & & & & & & & & & & & & & & & & & & &3 \\ \hline
20& & & & & & & & & & & & & & & & & & & &  \\ \hline
\end{array}$
\vskip 0.05in

When I ran my progam with this input, I got the following output:
\begin{verbatim}
Start at 1
Move to 2 at cost 5
Move to 3 at cost 5
Move to 4 at cost 2
Move to 8 at cost 1
Move to 9 at cost 6
Move to 11 at cost 3
Move to 12 at cost 1
Move to 13 at cost 2
Move to 16 at cost 1
Move to 17 at cost 3
Move to 19 at cost 6
Move to 20 at cost 3

Start at 1
Move to 5 at cost 8
Move to 6 at cost 6
Move to 7 at cost 1
Move to 10 at cost 1
Move to 14 at cost 1
Move to 15 at cost 8
Move to 18 at cost 1
Move to 20 at cost 3

Total cost: 67
\end{verbatim}

}

\begin{small}
\bibliographystyle{plain}
%\bibliography{../../Research/dstrbtd}
\bibliography{smawk}
\end{small}

\end{document}
