0x61最短路

对于一张有向图①，我们一般有邻接矩阵和邻接表两种存储方式。对于无向图，可以把无向边看作两条方向相反的有向边，从而采用与有向图一样的存储方式。因此，在讨论最短路问题时，我们都以有向图为例。

设有向图 $G = (V, E)$ ， $V$ 是点集， $E$ 是边集， $(x, y)$ 表示一条从 $x$ 到 $y$ 的有向边，其边权（或称长度）为 $w(x, y)$ 。设 $n = |V|$ ， $m = |E|$ ，邻接矩阵 $A$ 是一个 $n * n$ 的矩阵，在本书中，我们把它定义为：

邻接矩阵的空间复杂度为 $O(n^{2})$ 。

我们在0x13节中已经讲解过了“邻接表”，并用数组模拟链表的形式进行了代码实现。长度为 $n$ 的表头数组head记录了从每个节点出发的第一条边在ver和edge数组中的存储位置，长度为 $m$ 的边集数组ver和edge记录了每条边的终点和边权，长

度为 $m$ 的数组 next 模拟了链表指针，表示从相同节点出发的下一条边在 ver 和 edge 数组中的存储位置。邻接表的空间复杂度为 $O(n + m)$ 。

// 加入有向边(x, y)，权值为z  
void add(int x, int y, int z) {  
    ver[++tot] = y, edge[tot] = z; // 真实数据  
    next[tot] = head[x], head[x] = tot; // 在表头x处插入  
}

// 访问从  $\mathbf{x}$  出发的所有边  
for (int i = head[x]; i; i = next[i]) {  
    int y = ver[i], z = edge[i];  
    // 找到了一条有向边(x, y)，权值为z  
}

$\spadesuit$ 单源最短路径

单源最短路径问题（Single Source Shortest Path，SSSP 问题）是说，给定一张有向图 $G = (V, E)$ ， $V$ 是点集， $E$ 是边集， $|V| = n$ ， $|E| = m$ ，节点以 $[1, n]$ 之间的连续整数编号， $(x, y, z)$ 描述一条从 $x$ 出发，到达 $y$ ，长度为 $z$ 的有向边。设 1 号点为起点，求长度为 $n$ 的数组 $dist$ ，其中 $dist[i]$ 表示从起点 1 到节点 $i$ 的最短路径的长度。

Dijkstra 算法

Dijkstra 算法的流程如下：

1. 初始化 $dist[1] = 0$ ，其余节点的dist值为正无穷大。

2. 找出一个未被标记的、dist[x] 最小的节点 $x$ ，然后标记节点 $x$ 。

3. 扫描节点 $x$ 的所有出边 $(x, y, z)$ ，若 $dist[y] > dist[x] + z$ ，则使用 $dist[x] + z$ 更新 $dist[y]$ 。

4. 重复上述两个步骤，直到所有节点都被标记。

Dijkstra 算法基于贪心思想，它只适用于所有边的长度都是非负数的图。当边长 $z$ 都是非负数时，全局最小值不可能再被其他节点更新，故在第 1 步中选出的节点 $x$ 必然满足： $dist[x]$ 已经是起点到 $x$ 的最短路径。我们不断选择全局最小值进行标记和扩展，最终可得到起点 1 到每个节点的最短路径的长度。

int a[3010][3010], d[3010], n, m;  
bool v[3010];

void dijkstra(){memset(d,0x3f,sizeof(d));//dist数组memset(v,0,sizeof(v)); //节点标记  $d[1] = 0$  · for(int  $\mathrm{i} = 1$  ；i<n；i++){ //重复进行n-1次 int  $\mathbf{x} = \mathbf{0}$  //找到未标记节点中dist最小的 for(int  $\mathrm{j} = 1$  ；j<=n；j++) if(!v[j]&&(x==0||d[j]<d[x]))x=j; v[x]=1; //用全局最小值点  $\mathbf{x}$  更新其他节点 for(inty=1；y<=n；y++) d[y]=min(d[y],d[x]+a[x][y]); }   
}   
int main() { cin >> n>>m; //构建邻接矩阵memset(a,0x3f,sizeof(a)); for (int i=1;i<=n;i++) a[i][i]=0; for (int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][y]=min(a[x][y],z); } //求单源最短路径 dijkstra(); for (int i=1;i<=n;i++) printf("%d\n",d[i]);

上面程序的时间复杂度为 $O(n^{2})$ ，主要瓶颈在于第1步的寻找全局最小值的过程。可以用二叉堆（C++ STLpriority_queue，0x71节）对dist数组进行维护，用 $O(\log n)$ 的时间获取最小值并从堆中删除，用 $O(\log n)$ 的时间执行一条边的扩展和更新，最终可在 $O(m\log n)$ 的时间内实现Dijkstra算法。

const int N = 100010, M = 1000010;  
int head[N], ver[M], edge[M], Next[M], d[N];  
bool v[N];  
int n, m, tot;  
//大根堆（优先队列），pair的第二维为节点编号  
//pair的第一维为dist的相反数（利用相反数变成小根堆，参见0x71节）  
priority_queue<int, int> > q;  
void add(int x, int y, int z) {  
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;  
}  
void dijkstra() {  
    memset(d, 0x3f, sizeof(d)); //dist数组  
    memset(v, 0, sizeof(v)); //节点标记  
    d[1] = 0;  
    q.push(make_pair(0, 1));  
    while (q.size()) {  
        //取出堆顶  
        int x = q.top().second; q.pop();  
        if (v[x]) continue;  
        v[x] = 1;  
        //扫描所有出边  
        for (int i = head[x]; i; i = Next[i]) {  
            int y = ver[i], z = edge[i];  
            if (d[y] > d[x] + z) {  
                //更新，把新的二元组插入堆  
                d[y] = d[x] + z;  
                q.push(make_pair(-d[y], y));  
            }  
        }  
    }  
}

int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);   
}   
//求单源最短路径   
dijkstra();   
for (int i = 1; i <= n; i++) printf("%d\n",d[i]);   
}

Bellman-Ford算法和SPFA①算法

给定一张有向图，若对于图中的某一条边 $(x,y,z)$ ，有 $dist[y] \leq dist[x] + z$ 成立，则称该边满足三角形不等式。若所有边都满足三角形不等式，则 $dist$ 数组就是所求最短路。

我们先介绍基于迭代思想的Bellman-Ford算法。它的流程如下：

1. 扫描所有边 $(x, y, z)$ , 若 $dist[y] > dist[x] + z$ , 则用 $dist[x] + z$ 更新 $dist[y]$ 。

2. 重复上述步骤，直到没有更新操作发生。

Bellman-Ford算法的时间复杂度为 $O(nm)$ 。

实际上，SPFA算法在国际上通称为“队列优化的Bellman-Ford算法”，仅在中国大陆地区流行“SPFA算法”的称谓。请读者回顾0x26节对“广搜变形”的讨论与总结。SPFA算法的流程如下：

1. 建立一个队列，最初队列中只含有起点 1。

2. 取出队头节点 $x$ ，扫描它的所有出边 $(x, y, z)$ ，若 $dist[y] > dist[x] + z$ ，则使用 $dist[x] + z$ 更新 $dist[y]$ 。同时，若 $y$ 不在队列中，则把 $y$ 入队。

3. 重复上述步骤，直到队列为空。

在任意时刻，该算法的队列都保存了待扩展的节点。每次入队相当于完成一次dist数组的更新操作，使其满足三角形不等式。一个节点可能会入队、出队多次。最终，图中节点收敛到全部满足三角形不等式的状态。这个队列避免了Bellman-Ford算法中对不需要扩展的节点的冗余扫描，在稀疏图上运行效率较高，为 $O(km)$ 级别，其中 $k$ 是一个较小的常数。但在稠密图或特殊构造的网格图上，该算法仍可能退化为 $O(nm)$ 。

const int N = 100010, M = 1000010;  
int head[N], ver[M], edge[M], Next[M], d[N];  
int n, m, tot;

queue<int>q;   
bool v[N];   
void add(int x,int y,int z){ ver  $\mathrm{[ + + t o t ] = y}$  edge[tot]  $= z$  Next[tot]=head[x],head[x]=tot;   
}   
void spfa(){ memset(d,0x3f,sizeof(d));//dist数组 memset(v,0,sizeof(v));//是否在队列中 d[1]  $= 0$  ：v[1]  $= 1$  q.push(1); while (q.size()){ //取出队头 int  $\mathbf{x} = \mathbf{q}$  .front();q.pop();  $\mathrm{v[x] = 0}$  //扫描所有出边 for (int i = head[x];i；i = Next[i]) { int  $\mathrm{y} = \mathrm{ver}[\mathrm{i}]$  ，z  $=$  edge[i]; if  $(\mathrm{d[y] > d[x] + z})$  { //更新，把新的二元组插入堆  $\mathrm{d[y] = d[x] + z};$  if(!v[y])q.push(y)，v[y]  $= 1$  1 } }   
}   
}   
int main() { cin >> n >> m; //构建邻接表 for (int i  $= 1$  ;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } //求单源最短路径 spfa();

for (int i = 1; i <= n; i++) printf("%d\n", d[i]);

即使图中存在长度为负数的边，Bellman-Ford 和 SPFA 算法也能够正常工作，只不过时间复杂度会进一步增加。有一个名为 SLF 的优化策略，它基于双端队列的思想，在每次更新 $dist[y]$ 之后，把 $dist[y]$ 与当前队头节点（即把 $x$ 出队以后，队头的那个节点）的 $dist$ 值进行比较。若 $dist[y]$ 更小，则从队头把 $y$ 入队，否则仍从队尾入队。一般情况下，SLF 优化能略微提高 SPFA 算法的运行效率。

如果图中不存在长度为负数的边，那么类似于优先队列BFS，我们也可以使用二叉堆（C++ STLpriority_queue）对SPFA算法进行优化，堆代替了一般的队列，用于保存待扩展的节点，每次取出“当前距离最小”的节点（堆顶）进行扩展，节点第一次从堆中被取出时，就得到了该点的最短路。这与堆优化Dijkstra算法的流程完全一致。“二叉堆优化基于贪心的Dijkstra算法”和“优先队列优化基于BFS的SPFA算法”两种思想殊途同归，都得到了非负权图上 $O(m \log n)$ 的单源最短路径算法。

【例题】Telephone Lines POJ3662

在郊区有 $N$ 座通信基站, $P$ 条双向电缆, 第 $i$ 条电缆连接基站 $A_{i}$ 和 $B_{i}$ 。特别地, 1 号基站是通信公司的总站, $N$ 号基站位于一座农场中。现在, 农场主希望对通信线路进行升级, 其中升级第 $i$ 条电缆需要花费 $L_{i}$ 。

电话公司正在举行优惠活动。农场主可以指定一条从1号基站到 $N$ 号基站的路径，并指定路径上不超过 $K$ 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。

简单来说，本题是在无向图上求出一条从1到 $N$ 的路径，使路径上第 $K + 1$ 大的边权尽量小。

解法一

可以仿照动态规划的思想，用 $D[x,p]$ 表示从1号节点到达基站 $x$ ，途中已经指定了 $p$ 条电缆免费时，经过的路径上最贵的电缆的花费最小是多少（也就是选择一条从1到 $x$ 的路径，使路径上第 $p + 1$ 大的边权尽量小）。若有一条从 $x$ 到 $y$ 长度为 $z$ 的无向边，则应该用 $\max (D[x,p],z)$ 更新 $D[y,p]$ 的最小值，用 $D[x,p]$ 更新 $D[y,p + 1]$ 的最小值。前者表示不在电缆 $(x,y,z)$ 上使用免费升级服务，后者表示使用。

0x50章“动态规划”的开头曾指出，所谓“无后效性”其实告诉我们，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。显然，我们刚才设计的状态转移是有后效性的。在有后效性时，一种解决方案就是利用迭代思想，借助SPFA算法进行动态规划，直至所有状态收敛（不能再更新）。

从最短路问题的角度去理解，图中的节点也不仅限于“整数编号”，可以扩展到二维，用二元组 $(x,p)$ 代表一个节点，从 $(x,p)$ 到 $(y,p)$ 有长度为 $z$ 的边，从 $(x,p)$ 到 $(y,p + 1)$ 有长度为0的边。 $D[x,p]$ 表示从起点(1,0）到节点 $(x,p)$ ，路径上最长的边最短是多少。这是 $N*K$ 个点， $P*K$ 条边的广义单源最短路问题，使用SPFA算法，对于非特殊构造的数据，时间复杂度为 $O(tNP)$ ，其中 $t$ 为常数，实际测试可以AC。本题也让我们进一步领会了动态规划与最短路问题的共通性。

解法二

本题的答案显然具有单调性，因为支付的钱更多时，合法的升级方案一定包含了花费更少的升级方案。所以我们可以二分答案，把问题转化为：是否存在一种合法的升级方法，使花费不超过 $\text{mid}$ 。

转化后的判定问题非常容易。只需要把升级价格大于 mid 的电缆看作长度为 1 的边，把升级价格不超过 mid 的电缆看作长度为 0 的边，然后求从 1 到 $N$ 的最短路是否不超过 $K$ 即可。在 0x26 节我们已经学习过，可以用双端队列 BFS 求解这种边权只有 0 和 1 的最短路问题。整个算法时间复杂度为 $O((N + P) \log MAX_L)$ 。

【例题】最优贸易 NOIP2009/CODEVS1173

C 国有 $n$ 个大城市和 $m$ 条道路, 每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路, 一部分为双向通行的道路, 双向通行的道路在统计条数时也计为 1 条。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到C国旅游。当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。设C国 $n$ 个城市的标号从 $1 \sim n$ ，阿龙决定从1号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 $n$ 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。

因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 $n$ 个城市的水晶球价格, $m$ 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请你告诉阿龙, 他最多能赚取多少旅费。

数据范围： $1\leq n\leq 10^{5},1\leq m\leq 5*10^{5}$ 。

本题是让我们在一张节点带有权值的图上找出一条从1到 $n$ 的路径，使路径上能选出两个点 $p, q$ （先经过 $p$ 后经过 $q$ ），并且“节点 $q$ 的权值减去节点 $p$ 的权值”最大。

图中双向通行的道路可看作两条方向相反的单向通行道路。在下面的讨论中，我们均把这张图视为有向图。除此之外，我们再建立一张反图（在原图基础上把所有边的方向取反后得到的图）保存在另外一个邻接表中。

先以1为起点，在原图上用SPFA或Dijkstra算法，求出数组 $D$ ，其中 $D[x]$ 表示从节点1到节点 $x$ 的所有路径中，能够经过的权值最小的节点的权值。 $D$ 数组的计算过程与单源最短路径的计算过程类似，只需要把最短路中的“用 $D[x] + w(x,y)$ 更新 $D[y]$ ”改为“用 $\min(D[x], price[y])$ 更新 $D[y]$ ”即可，其中 $price[y]$ 表示点 $y$ 的商品价格。

再以 $n$ 为起点，在反图上用SPFA或Dijkstra算法，求出数组 $F$ ，其中 $F[x]$ 表示在原图上从节点 $\pmb{x}$ 到节点 $n$ （在反图上从 $\pmb{n}$ 到 $\pmb{x}$ ）的所有路径中，能够经过的权值最大的节点的权值。 $F$ 的计算方法与 $D$ 类似。

最后，枚举每个节点 $x$ ，用 $F[x] - D[x]$ 更新答案即可。

【例题】道路与航线 BZOJ2200

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T(1 \leq T \leq 25,000)$ 个城镇，编号为 $1 \sim T$ 。城镇之间通过 $R(1 \leq R \leq 50,000)$ 条道路和 $P(1 \leq P \leq 50,000)$ 条航线连接。每条道路或者航线连接城镇 $A_{i}$ 和 $B_{i}$ （ $1 \leq A_{i}, B_{i} \leq T$ ），花费为 $C_{i}$ 。对于道路， $0 \leq C_{i} \leq 10,000$ ，然而航线的花费很神奇，航线的 $C_{i}$ 可能是负数， $-10,000 \leq C_{i} \leq 10,000$ 。另外，道路都是双向的，航线都是单向的。

事实上，因为最近恐怖主义太嚣张，为了社会和谐，政府出台了一些政策保证：如果有一条航线可以从 $A_{i}$ 到 $B_{i}$ ，那么不可能通过一些道路和航线从 $B_{i}$ 回到 $A_{i}$ 。因为FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从中心城镇 $S(1\leq S\leq T)$ 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

本题是一道明显的单源最短路问题，但图中带有负权边，不能使用Dijkstra算法。若直接用SPFA算法求解，因为测试数据经过了特殊构造，所以程序无法在规定时限内

输出答案。题目中有一个特殊条件——双向边都是非负的，只有单向边可能是负的，并且单向边不构成环。我们应该利用这个性质来解答本题。

如果只把双向边（也就是题目中的“道路”）添加到图里，那么会形成若干个连通块。若把每个连通块整体看作一个“点”，再把单向边（也就是题目中的“航线”）添加到图里，会得到一张有向无环图。在有向无环图上，无论边权正负，都可以按照拓扑序进行扫描，在线性时间内求出单源最短路。这启发我们用拓扑序的框架处理整个图，但在双向边构成的每个连通块内部使用堆优化的Dijkstra算法快速计算该块内的最短路信息。

详细的算法流程如下：

1. 只把双向边加入到图中，用深度优先遍历划分图中的连通块（第0x21节），记 $c[x]$ 为节点 $x$ 所属的连通块的编号。

2. 统计每个连通块的总入度（有多少条边从连通块之外指向连通块之内），记 $\deg [i]$ 为第 $i$ 个连通块的总入度。

3. 建立一个队列（存储连通块编号，用于拓扑排序），最初队列中仅包含起点 $S$ 所在的连通块 $c[S]$ 。设 $d[S] = 0$ ，其余点的 $d$ 值为 $+\infty$ 。
   4.取出队头的连通块 $i$ ，对该连通块执行堆优化的Dijkstra算法，具体步骤为：

(1) 建立一个堆，把第 $i$ 个连通块的所有节点加入堆中。
(2) 从堆中取出 $d[x]$ 最小的节点 $x$ 。
(3) 若 $x$ 被扩展过，回到步骤(2)，否则进入下一步。
(4) 扫描从 $x$ 出发的所有边 $(x, y, z)$ ，用 $d[x] + z$ 更新 $d[y]$ 。
(5) 若 $c[x] = c[y]$ （仍在连通块内）并且 $d[y]$ 被更新，则把 $y$ 插入堆。
(6) 若 $c[x] \neq c[y]$ , 则令 $\deg[c[y]]$ 减去 1。若减到了 0, 则把 $c[y]$ 插入拓扑排序的队列末尾。
(7) 重复步骤(2)~(6)，直至堆为空。

1. 重复步骤4，直至队列为空，拓扑排序完成。

数组 $d$ 即为所求。整个算法的时间复杂度为 $\mathrm{O}(T + P + R\log T)$ 。

$\spadesuit$ 任意两点间最短路径

为了求出图中任意两点间的最短路径，当然可以把每个点作为起点，求解 $N$ 次单源最短路径问题。不过，在任意两点间最短路问题中，图一般比较稠密。使用Floyd算法可以在 $O(N^3)$ 的时间内完成求解，并且程序实现非常简单。

Floyd算法

设 $D[k,i,j]$ 表示“经过若干个编号不超过 $k$ 的节点”从 $i$ 到 $j$ 的最短路长度。

该问题可划分为两个子问题，经过编号不超过 $k - 1$ 的节点从 $i$ 到 $j$ ，或者从 $i$ 先到 $k$ 再到 $j$ 。于是：

初值为 $D[0,i,j] = A[i,j]$ ，其中 $A$ 为本节开头定义的邻接矩阵。

可以看到，Floyd算法的本质是动态规划。 $k$ 是阶段，所以必须置于最外层循环中。 $i$ 和 $j$ 是附加状态，所以应该置于内层循环。这也解释了为何很多初学者按照 $i, j, k$ 的顺序执行循环，会得到错误的结果。

与背包问题的状态转移方程类似， $k$ 这一维可被省略。最初，我们可以直接用 $D$ 保存邻接矩阵，然后执行动态规划的过程。当最外层循环到 $k$ 时，内层有状态转移：

最终 $D[i,j]$ 就保存了 $i$ 到 $j$ 的最短路长度。

int d[310][310], n, m;  
int main() {  
cin >> n >> m;  
// 把 d 数组初始化为邻接矩阵  
memset(d, 0x3f, sizeof(d));  
for (int i = 1; i <= n; i++) d[i][i] = 0;  
for (int i = 1; i <= m; i++) {  
    int x, y, z;  
    scanf("%d%d%d", &x, &y, &z);  
    d[x][y] = min(d[x][y], z);  
}  
// floyd 求任意两点间最短路径  
for (int k = 1; k <= n; k++)  
    for (int i = 1; i <= n; i++)  
        for (int j = 1; j <= n; j++)  
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  
// 输出  
for (int i = 1; i <= n; i++) {  
    for (int j = 1; j <= n; j++) printf("%d ", d[i][j]);  
    puts("");  
}

传递闭包

在交际网络中，给定若干个元素和若干对二元关系，且关系具有传递性①。“通过传递性推导出尽量多的元素之间的关系”的问题被称为传递闭包。

建立邻接矩阵 $d$ ，其中 $d[i,j] = 1$ 表示 $i$ 与 $j$ 有关系， $d[i,j] = 0$ 表示 $i$ 与 $j$ 没有关系。特别地， $d[i,i]$ 始终为1。使用Floyd算法可以解决传递闭包问题：

bool d[310][310];  
int n, m;  
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) d[i][i] = 1;  
    for (int i = 1; i <= m; i++) {  
        int x, y;  
        scanf("%d%d", &x, &y);  
        d[x][y] = d[y][x] = 1;  
    }  
    for (int k = 1; k <= n; k++)  
        for (int i = 1; i <= n; i++)  
            for (int j = 1; j <= n; j++)  
                d[i][j] |= d[i][k] & d[k][j];  
}

【例题】Sorting It All Out POJ1094

给定 $n$ 个变量， $m$ 个不等式。不等式之间具有传递性，即若 $A > B$ 且 $B > C$ 则 $A > C$ 。判断这 $m$ 个不等式是否有矛盾。若无矛盾，则判断这 $m$ 个不等式是否能确定每一对变量之间的关系。若能，则求出 $t$ 的最小值，满足仅用前 $t$ 个不等式就能确定每一对变量之间的大小关系。 $2 \leq n \leq 26$ 。

这是一道“有向”的传递闭包问题，需要在刚才思路的基础上稍作修改。对于每个形如 $i < j$ 的不等式，令 $d[i,j] = 1$ 。对于形如 $i > j$ 的不等式，看作 $j < i$ 进行处理。除了 $i < j$ 之外的情况，均有 $d[i,j] = 0$ 。

使用Floyd算法对 $d$ 进行传递闭包。传递闭包完成后，若存在变量 $i, j$ ，使得 $d[i, j]$ 和 $d[j, i]$ 均为1，则说明题目中给出的 $m$ 个不等式矛盾。若存在变量 $i, j$ ，使得 $d[i, j]$ 和 $d[j, i]$ 均为0，则说明题目中给出的 $m$ 个不等式不能确定每一对变量之间的大小

关系。

若对于每对变量 $i, j, d[i, j]$ 和 $d[j, i]$ 有且仅有一个为1，则说明能确定每对变量之间的大小关系。此时，可以再用二分法，二分 $t$ 的值，判断仅用前 $t$ 个不等式能否达到上述条件。

【例题】Sightseeing trip POJ1734

给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出“No solution.”。图的节点数不超过100。

考虑Floyd算法的过程。当外层循环 $k$ 刚开始时， $d[i,j]$ 保存着“经过编号不超过 $k - 1$ 的节点”从 $i$ 到 $j$ 的最短路长度。

于是， $\min_{1\leq i < j < k}\{d[i,j] + a[j,k] + a[k,i]\}$ 就是满足以下两个条件的最小环长度：

1. 由编号不超过 $k$ 的节点构成。

2. 经过节点 $k$ 。

上式中的 $i,j$ 相当于枚举了环上与 $k$ 相邻的两个点。故以上结论显然成立。

$\forall k \in [1, n]$ ，都对上式进行计算，取最小值，即可得到整张图的最小环。

在该算法中，我们对每个 $k$ 只考虑了由编号不超过 $k$ 的节点构成的最小环，没有考虑编号大于 $k$ 的节点。事实上，由对称性可知，这样做并不会影响结果。

int a[310][310], d[310][310], pos[310][310];  
int n, m, ans = 0x3f3f3f3f;  
vector<int> path; //具体方案  
void get_path(int x, int y) {  
    if (pos[x][y] == 0) return;  
    get_path(x, pos[x][y]);  
    path.push_back(pos[x][y]);  
    get_path(pos[x][y], y);  
}  
int main() {  
    cin >> n >> m;  
    memset(a, 0x3f, sizeof(a));  
    for (int i = 1; i <= n; i++) a[i][i] = 0;  
    for (int i = 1; i <= m; i++) {

int x, y, z;  
scanf("%d%d%d", &x, &y, &z);  
a[y][x] = a[x][y] = min(a[x][y], z);  
}  
memcpy(d, a, sizeof(a));  
for (int k = 1; k <= n; k++) {  
    for (int i = 1; i < k; i++)  
        for (int j = i + 1; j < k; j++)  
            if ((long long)d[i][j] + a[j][k] + a[k][i] < ans) {  
                ans = d[i][j] + a[j][k] + a[k][i];  
                path.clear();  
                path.push_back(i);  
                get_path(i, j);  
                path.push_back(j);  
                path.push_back(k);  
    }  
    for (int i = 1; i <= n; i++)  
        for (int j = 1; j <= n; j++)  
            if (d[i][j] > d[i][k] + d[k][j]) {  
                d[i][j] = d[i][k] + d[k][j];  
                pos[i][j] = k;  
    }  
}  
if (ans == 0x3f3f3f3f) {  
    puts("No solution.", return 0);  
}  
for (int i = 0; i < path.size(); i++)  
    printf("%d", path[i]);  
puts("");

对于有向图的最小环问题，可枚举起点 $s = 1 \sim n$ ，执行堆优化的 Dijkstra 算法求解单源最短路径。 $s$ 一定是第一个被从堆中取出的节点，我们扫描 $s$ 的所有出边，当扩展、更新完成后，令 $d[s] = +\infty$ ，然后继续求解。当 $s$ 第二次被从堆中取出时， $d[s]$ 就是经过点 $s$ 的最小环长度。

【例题】CowRelaysPOJ3613

给定一张由 $T(2 \leq T \leq 100)$ 条边构成的无向图，点的编号为 $1 \sim 1000$ 之间的整数。求从起点 $S$ 到终点 $E$ 恰好经过 $N(2 \leq N \leq 10^{6})$ 条边（可以重复经过）的最短路。

虽然点的编号在 $1 \sim 1000$ 之间，但边最多只有 100 条。我们可以先对点的编号进行离散化，把点的编号映射为 $1 \sim P$ 的整数，其中 $P \leq 2T$ 。

在离散化后，设 $P * P$ 的邻接矩阵 $A$ 存储了图中的边。考虑以下方程：

我们可以认为 $A[i,j]$ 表示从 $i$ 到 $j$ 经过1条边的最短路。在上面的方程中，对于每对二元组 $(i,j)$ ，我们枚举了中转点 $k$ ，从 $i$ 先到 $k$ ，然后再到 $j$ 。因此 $B[i,j]$ 表示从 $i$ 到 $j$ 经过2条边的最短路。

一般地，若矩阵 $A^m$ 保存任意两点之间恰好经过 $m$ 条边的最短路，则：

回顾 $0 \times 34$ 节“矩阵乘法”，我们发现，上式其实等价于一个关于 $\min$ 与加法运算的广义“矩阵乘法”。显然，这个广义的“矩阵乘法”也满足结合律。因此，我们可以用快速幂计算出 $A^{N}$ ，具体的实现方法就是：在计算一般的矩阵的幂的基础上，把原来的乘法用加法代替，把原来的加法用 $\min$ 运算代替。

最后， $(A^{N})[S,E]$ 即为本题的答案。整个算法的时间复杂度为 $O(T^{3}\log N)$ 。