\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年12月13日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\begin{document}

\textbf{Q1.}

将 $\textsc{Floyd-Warshall}$ 算法空间需求降低到 $\Theta(n^2)$ 改
为 $\textsc{Floyd-Warshall-New}$ 算法是正确的.

\begin{proof}
    要证明改进算法正确性，只需要证明原算法中将 $d_{ij}^{(k)}$ 在原
    地修改也不会更改算法的正确性.

    注意到算法中，$d_{ij}^{(k)}$ 的值会在第 $k$ 次迭代中被修改为
    $d_{ij}^{(k-1)}$ 和 $d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$ 中的较小
    值，而如果在原地修改，则也依然为 $d_{ij}$ 和 $d_{ik}+d_{kj}$
    中较小值.同时，此处的 $d_{ij}$，也就是 $d_{ij}^{(k-1)}$，并不
    会影响后续迭代.因此修改后的算法是正确的.
\end{proof}

\hrulefill\medskip

\textbf{Q2.}

如下算法，时间复杂度为 $O(|V|+k|E|)$.

\begin{algorithm}[ht]
    \caption{最短路算法}
    \KwIn{有向图 $G=(V,E,w)$ 和顶点 $s\in V$}
    \KwOut{从 $s$ 到每个 $v\in V$ 的最短路径权重 $d[v]$}
    \For{$v\in V$}{
        $d[v]\leftarrow\infty$\;
        $visited[v]\leftarrow$ false\;
    }
    $d[s]\leftarrow 0$\;
    $visited[s]\leftarrow$ true\;
    $Q\leftarrow\{s\}$\;
    \For{$i\leftarrow 1$ \KwTo$k$}{
    \For{$u\in Q$}{
    \For{$(u,v) \in E$}{
    \If{$d[v]>d[u]+w(u, v)$}{
    $d[v]\leftarrow d[u]+w(u,v)$\;
    }
    \If{not $visited[v]$}{
        $Q\leftarrow Q\bigcup\{v\}$\;
        $visited[v]\leftarrow$ true\;
    }
    }
    }
    }
    \Return{$d$}\;
\end{algorithm}

\textbf{Q3.}

\begin{proof}
    因为图 $G$ 包含一条权重为 $0$ 的环路 $c$，则从新增节点 $s$ 到
    环路 $c$ 上每个顶点 $u$ 的最短路径权重 $h(u)$ 应相同，否则，若
    某个顶点 $v$ 权重比其他的高，那么总可以从权重最低顶点沿着环路
    到达该顶点 $v$，使得最短路径权重 $h(v)$ 等于最短路径权重最低的
    那个值.因此对于环路上每条边 $(u,v)$，有 $\hat{w}(u,v)=w(u,v)+h(u)-h(v)=0+0=0$.
\end{proof}

\hrulefill\medskip

\textbf{Q4.}

对地图作如下变化，新图中有 $gn$ 个顶点，每个顶点记为 $(v,p)$，其中
$v$ 对应原图中的 $n$ 个站点，每个站点编号分别为 $1,2,\ldots,n$，
$p$ 为小曹在该点的体力值，因为要求严格保留正量体力值，取值为 $1,2,\ldots,g$；
而对于新图中的边，如果原本有一条边 $\langle u,v\rangle$，耗时间为
$t$，记 $\Delta e=\max(0,e_v-e_u)$，则在新图中会有对应的
$\langle(u,p_u),(v,p_u-\Delta e)\rangle,p_u=\Delta e+1,\Delta e+2,\ldots,g$
共计 $g-\Delta e$ 条边，这些边都记为耗时 $t$；如果原本站点 $v$ 有
补给点，则在新图中会有对应的 $\langle (v,p),(v,p+1)\rangle,p=1,2,\ldots,g-1$
共计 $g-1$ 条边，每条边耗时为 $t_G$.

然后在新图上调用 Dijkstra 算法，从点 $(s,g)$ 开始，求出其到所有点
最短路径后，取从该点出发到 $(t,p),p=1,2,\ldots,g$ 中最短路最少的一个即可.

时间复杂度上，Dijkstra 算法时间复杂度为 $O(|E|+|V|\lg|V|)$，新图
总共有 $O(gn)=O(n^2)$ 个顶点，有 $O(gr+gn)=O(5n^2+n^2)=O(n^2)$ 条边，
因此总时间复杂度为 $O(n^2+n^2\lg(n^2))=O(n^2\lg n)$.

\end{document}