题目分析

题意简述

给定若干个网络的信息，每个网络是一个最多包含 $n$（$3 \leq n \leq 100$）个顶点的连通图，通过邻接矩阵表示图中各边的权重（邻接矩阵中元素 $w_{u,v} > 0$ 表示顶点 $u$ 和 $v$ 之间有边且权重为 $w_{u,v}$，$w_{u,v} = 0$ 表示无边）。同时给定每个网络中一条最短路径的顶点序列，需要找出该最短路径上的迂回关键边（移除该边后会使相邻顶点到目标顶点的距离增量最大的边），并输出这个最大的距离增量。

输入

• 第一行输入整数 $T$，表示测试用例的数量。
• 对于每个测试用例：
  • 首先输入整数 $n$，表示网络中顶点的数量。
  • 接下来的 $n$ 行，每行输入 $n$ 个整数，构成网络的邻接矩阵 $adj[i][j]$。
  • 最后一行输入一个顶点序列的字符串，解析出最短路径上的顶点编号序列 $sp$。

输出

对于每个测试用例，输出一行，为该测试用例中给定最短路径的迂回关键边所导致的最大距离增量。

解题思路

计算最短路径距离

1. 首先读取每个测试用例的顶点数量 $n$ 和邻接矩阵 $adj$。
2. 读取最短路径的顶点序列字符串，解析并存入数组 $sp$ 中。
3. 确定目标顶点 $dest$ 为最短路径序列的最后一个顶点 $sp[spn - 1]$。
4. 从目标顶点开始向前遍历最短路径序列，计算每个顶点到目标顶点的最短路径距离 $minDist$。对于顶点 $i$，其到目标顶点的距离 $minDist[i] = adj[sp[i]][sp[i + 1]] + minDist[i + 1]$（$i$ 从 $spn - 2$ 到 $0$），其中 $minDist[spn - 1] = 0$。

计算迂回路径距离并找最大增量

1. 对于最短路径上的每一条边（从起点到倒数第二个顶点），移除该边后使用迪杰斯特拉算法计算起点顶点到目标顶点的距离 $estmDist$：
   • 初始化估计距离数组 $estmDist$，将当前顶点的距离设为 $0$，其他顶点设为一个很大的值（$2147483647$）。
   • 遍历所有顶点，更新与当前顶点相邻的顶点的估计距离（跳过要移除的边的另一个顶点）。
   • 使用迪杰斯特拉算法的核心步骤，不断选择未访问且距离最小的顶点，更新其相邻顶点的距离，直到访问到目标顶点或所有顶点都被访问。
2. 计算移除该边后的距离与原最短路径距离的差值 $detour = estmDist[dest] - minDist[i]$。
3. 记录所有边的距离差值中的最大值 $maxDetour$。

输出结果

输出每个测试用例的最大距离增量 $maxDetour$。

代码实现

#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
using namespace std;

int main() {
    int T;
    cin >> T;
    for(int ii = 0; ii < T; ii++){
        int n;
        cin >> n;
        int adj[110][110];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> adj[i][j];
            }
        }
        int sp[110];
        int spn = 0;
        string s;
        while(1){
            while(getline(cin, s)){
                if(s.length()) break;
            }
            stringstream ss;
            ss << s;
            while(ss >> sp[spn]){
                spn++;
            }
            if(spn) break;
        }
        //for(int i = 0; i < spn; i++) cout << sp[i] << " "; cout << endl;
        int dest = sp[spn-1];
        //cout << dest << endl;
        int minDist[110];
        minDist[spn-1] = 0;
        for(int i = spn-2; i >= 0; i--){
            minDist[i] = adj[sp[i]][sp[i+1]] + minDist[i+1];
        }
        //for(int i = 0; i < spn; i++) cout << minDist[i] << " " ; cout << endl;
        int maxDetour = 0;
        for(int i = 0; i < spn-1; i++){
            //最小距离是minDist[i]
            //下面是dj
            int estmDist[110];
            for(int j = 1; j <= n; j++) estmDist[j] = 2147483647;
            estmDist[sp[i]] = 0;
            for(int j = 1; j <= n; j++){
                if(j == sp[i+1]) continue;
                if((adj[sp[i]][j] > 0) && (adj[sp[i]][j] < estmDist[j])) estmDist[j] = adj[sp[i]][j];
            }
            bool used[110] = {0};
            used[sp[i]] = 1;
            for(int j = 0; j < n-1; j++){
                int mnDist = 2147483647, arg = -1;
                for(int k = 1; k <= n; k++){
                    if(used[k]) continue;
                    if(estmDist[k] < mnDist){
                        mnDist = estmDist[k];
                        arg = k;
                    }
                }
                if(arg == -1) break;
                used[arg] = 1;
                if(arg == dest) break;
                for(int k = 1; k <= n; k++){
                    if(used[k]) continue;
                    if((adj[arg][k] > 0) && (estmDist[k] > estmDist[arg] + adj[arg][k])){
                        estmDist[k] = estmDist[arg] + adj[arg][k];
                    }
                }
            }
            int detour = estmDist[dest] - minDist[i];
            if(maxDetour < detour) maxDetour = detour;
        }
        cout << maxDetour << endl;
    }
    return 0;
}

代码说明

1. 变量定义：
   • T：存储测试用例的数量。
   • n：每个测试用例中网络的顶点数量。
   • adj[110][110]：邻接矩阵，存储网络中顶点之间的边的权重。
   • sp[110]：存储最短路径的顶点序列。
   • spn：最短路径顶点序列的长度。
   • s：用于存储读取的顶点序列字符串。
   • dest：最短路径的目标顶点。
   • minDist[110]：存储最短路径上每个顶点到目标顶点的最短距离。
   • estmDist[110]：在移除某边后使用迪杰斯特拉算法计算的估计距离。
   • used[110]：标记顶点是否已被访问过的数组。
   • maxDetour：记录最大的距离增量。
2. 输入处理：
   • 读取测试用例数量 $T$。
   • 对于每个测试用例，读取顶点数量 $n$ 和邻接矩阵的元素。
   • 读取最短路径的顶点序列字符串，使用 stringstream 解析字符串并将顶点编号存入 sp 数组。
3. 最短路径距离计算：
   • 确定目标顶点 dest。
   • 从目标顶点开始向前计算每个顶点到目标顶点的最短路径距离 minDist。
4. 迂回路径距离计算与最大增量查找：
   • 遍历最短路径上的每一条边（除最后一条）。
   • 移除当前边后，使用迪杰斯特拉算法计算起点顶点到目标顶点的估计距离 estmDist。
   • 计算移除边后的距离与原最短路径距离的差值 detour，更新最大距离增量 maxDetour。
5. 输出结果：输出每个测试用例的最大距离增量 maxDetour。