前置知识:最短路径

step1.动画理解Dijstra算法

step2.实现Dijstra算法(C++/Python)

题面描述:

有两个相邻的国家 $A$ 和 $B$，其中有 $N$ 个城市，编号为 $1$ 到 $N$。$M$ 条公路连接这些城市，其中有些是国内公路，有些是连接 $A$ 国与 $B$ 国边界城市的跨国公路。每条公路有一个距离和花费。

你需要帮助小塔从 $A$ 国的城市 $1$（城市 $1$）到达 $B$ 国的城市 $N$，但由于只能办理一次入境签证，小塔在旅行中只能通过一条跨国公路。你需要找到一条使总距离最短的路径，并在距离相同的情况下使花费最少。如果小塔无法到达城市 $N$，输出 $-1$。

思路:枚举 + Dijstra最短路

1.根据数据范围，我们可以使用朴素的Dijkstra算法，分别计算从起点1和终点n到其他节点的属于同一个城市的图集合的最短路径。得到两个数组:dist_1,dist_n

2.枚举所有跨城市的边(u , v)，考虑使用1 -> u + v -> n 更新最小值。最后输出即可。

3.这里我们的比较大小逻辑需要替换成:x[0] < y[0] or (x[0] == y[0] and x[1] < y[1])

题解

本题的核心是让小塔从城市 1 到城市 N，并且只能通过一条跨国公路。每条公路有一个距离和花费的属性。我们需要找到使得距离最短的路径，并在距离相同的情况下使花费最少。

思路分析

1. 拆分问题：

   • 由于小塔只能通过一条跨国公路，我们可以把问题拆解为两个部分：分别计算小塔在 $A$ 国和 $B$ 国的最短路径。也就是说，我们可以分别计算从城市 1（属于 $A$ 国）到 $A$ 国其他城市的最短路径，以及从城市 $N$（属于 $B$ 国）到 $B$ 国其他城市的最短路径。
   • 跨国的路径只能通过一条跨国公路连接 $A$ 国和 $B$ 国。因此，最终的路径可以表示为：1 -> u（$A$ 国的城市） + 跨国公路 u -> v + v -> N（$B$ 国的城市）。

2. 分解为子问题：

   • 我们可以将问题分解为在 $A$ 国和 $B$ 国的子图上分别求最短路径的问题。使用朴素的 Dijkstra 算法，我们可以分别计算从起点城市 1 和终点城市 N 到各个节点的最短路径。
   • 计算得到两个数组 dist_1 和 dist_n，分别表示从城市 1 出发的最短路径和从城市 N 出发的最短路径。
   • 然后我们只需枚举所有跨国公路，检查通过每一条跨国公路的路径是否能形成更优的解。

3. 比较更新最优解：

   • 由于需要在距离相同的情况下优先选择花费最少的路径，因此我们定义一个 lower 函数，来对比两个路径的优劣。优先比较距离，若距离相同则比较花费。
   • 最后，遍历所有跨国公路，利用公式 1 -> u + u -> v + v -> N 更新全局最优解。

代码

c++

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;

struct Edge {
    int to, dist, cost;
};

bool lower(pair<int, int> x, pair<int, int> y) {
    // 比较两个 pair (距离, 花费)，距离小的优先，距离相同则比较花费
    return x.first < y.first || (x.first == y.first && x.second < y.second);
}

int n, m;
vector<char> city_type;
vector<vector<Edge>> graph;
vector<tuple<int, int, int, int>> trans_edge; // 存储跨城市的边

vector<pair<int, int>> dijstra(int start) {
    // 初始化距离数组，每个城市的距离和代价初始为无穷大
    vector<pair<int, int>> distance(n + 1, {INT_MAX, INT_MAX});
    distance[start] = {0, 0};  // 起点的距离和代价为0
    vector<bool> visited(n + 1, false);  // 记录每个节点是否已经访问过

    for (int i = 1; i <= n; i++) {
        // 找到当前未访问节点中距离最小的节点
        pair<int, int> min_distance = {INT_MAX, INT_MAX};
        int min_index = -1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && lower(distance[j], min_distance)) {
                min_distance = distance[j];
                min_index = j;
            }
        }

        if (min_index == -1) break; // 所有节点都访问过，或者不可达
        visited[min_index] = true;  // 标记该节点为已访问

        // 更新与当前节点相邻的其他节点的距离
        for (auto &edge : graph[min_index]) {
            int to = edge.to, w = edge.dist, c = edge.cost;
            if (visited[to] || city_type[to] != city_type[min_index]) continue; // 不同国，跳过
            pair<int, int> new_distance = {distance[min_index].first + w, distance[min_index].second + c};
            if (lower(new_distance, distance[to])) {
                distance[to] = new_distance;
            }
        }
    }
    return distance;
}

int main() {
    cin >> n >> m;
    city_type.resize(n + 1);
    graph.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> city_type[i];
    }

    for (int i = 0; i < m; i++) {
        int a, b, w, c;
        cin >> a >> b >> w >> c;
        graph[a].push_back({b, w, c});
        graph[b].push_back({a, w, c});

        // 如果 a 和 b 属于不同的国家，记录这条跨城市的边
        if (city_type[a] != city_type[b]) {
            trans_edge.push_back({a, b, w, c});
            trans_edge.push_back({b, a, w, c});
        }
    }

    // 计算从城市 1 和 n 出发的最短路径
    vector<pair<int, int>> distance_1 = dijstra(1);
    vector<pair<int, int>> distance_n = dijstra(n);

    // 初始化答案
    pair<int, int> ans = {INT_MAX, INT_MAX};

    // 遍历所有跨城市的边，更新最短路径
    for (auto &edge : trans_edge) {
        int a, b, w, c;
        tie(a, b, w, c) = edge;
        if (distance_1[a].first == INT_MAX || distance_n[b].first == INT_MAX) continue; // 不可达
        pair<int, int> new_ans = {distance_1[a].first + distance_n[b].first + w, distance_1[a].second + distance_n[b].second + c};
        if (lower(new_ans, ans)) {
            ans = new_ans;
        }
    }

    // 输出结果
    if (ans.first == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << ans.first << " " << ans.second << endl;
    }

    return 0;
}

python

def lower(x, y):
    # 定义一个比较函数，用于比较两个距离和代价对。
    # 返回 True 表示 x 比 y 小，规则是先比较距离，如果距离相同则比较代价。
    return x[0] < y[0] or (x[0] == y[0] and x[1] < y[1])

# 输入处理，读取城市数量 n 和边的数量 m
n = int(input())
m = int(input())

# 读取每个城市的类型（属于同一个城市类型的节点才能互相通行），并在开头加上一个占位符"X"
city_type = list(input())
city_type = ["X"] + city_type

# 初始化图的邻接矩阵，graph[i][j]表示城市i到城市j的距离和代价对，初始值为[-1, -1]表示没有路径
graph = [[[-1, -1] for _ in range(n + 1)] for _ in range(n + 1)]

# 初始化跨城市的边集合（用于最后跨城市的更新）
trans_edge = []

# 读取所有边的信息
for i in range(m):
    a, b, w, c = map(int, input().split())  # 读取起点a，终点b，边的距离w，边的代价c
    if graph[a][b][0] != -1:  # 如果a和b之间已经有一条边
        # 比较当前读入的边和已有的边，取距离更小且代价更低的边
        if lower([w, c], graph[a][b]):
            graph[a][b] = [w, c]
            graph[b][a] = [w, c]  # 更新a到b和b到a的边信息
    else:
        # 如果a和b之间没有边，直接更新边的信息
        graph[a][b] = [w, c]
        graph[b][a] = [w, c]
    
    # 如果a和b属于不同的城市类型，记录这条跨城市的边
    if city_type[a] != city_type[b]:
        trans_edge.append([a, b, w, c])
        trans_edge.append([b, a, w, c])

# 朴素的Dijkstra算法，用于计算从起点到其他节点的最短路径
def dijstra(start, city_type):
    # 初始化距离数组，每个城市的距离和代价初始为无穷大
    distance = [[float('inf'), float('inf')] for _ in range(n + 1)]
    distance[start] = [0, 0]  # 起点的距离和代价为0
    visited = [False] * (n + 1)  # 记录每个节点是否已经访问过
    
    # Dijkstra算法的主要部分
    for i in range(1, n + 1):
        # 找到当前未访问节点中距离最小的节点
        min_distance = [float('inf'), float('inf')]
        min_index = -1
        for j in range(1, n + 1):
            if not visited[j]:
                if lower(distance[j], min_distance):
                    min_distance = [distance[j][0], distance[j][1]]
                    min_index = j

        visited[min_index] = True  # 标记该节点为已访问

        # 更新与当前节点相邻的其他节点的距离
        for j in range(1, n + 1):
            if visited[j]:
                continue
            if graph[min_index][j][0] == -1:  # 如果当前节点和j之间没有边，跳过
                continue
            if city_type[j] != city_type[min_index]:  # 如果节点j和当前节点不属于同一个城市类型，跳过
                continue
            # 更新节点j的距离和代价，取较小的值
            if lower([distance[min_index][0] + graph[min_index][j][0], distance[min_index][1] + graph[min_index][j][1]], distance[j]):
                distance[j] = [distance[min_index][0] + graph[min_index][j][0], distance[min_index][1] + graph[min_index][j][1]]
    return distance  # 返回从start节点出发的最短路径结果

# 计算从起点1和终点n到其他节点的最短路径
distance_1 = dijstra(1, city_type)
distance_n = dijstra(n, city_type)

# 初始化答案，表示最终的最小距离和代价对，初始值为无穷大
ans = [float('inf'), float('inf')]

# 遍历所有跨城市的边，更新最短路径
for edge in trans_edge:
    a, b, w, c = edge  # 读取跨城市边的起点a，终点b，边的距离w，边的代价c
    # 如果从起点1到a或从终点n到b的距离是无穷大，跳过（表示不可达）
    if distance_1[a][0] == float('inf') or distance_n[b][0] == float('inf'):
        continue
    # 尝试通过这条跨城市边更新最小距离和代价，比较并取最优解
    if lower([distance_1[a][0] + distance_n[b][0] + w, distance_1[a][1] + distance_n[b][1] + c], ans):
        ans = [distance_1[a][0] + distance_n[b][0] + w, distance_1[a][1] + distance_n[b][1] + c]

# 如果答案的距离仍然是无穷大，说明没有可行路径，输出-1；否则输出最小距离和代价
if ans[0] == float('inf'):
    print(-1)
else:
    print(ans[0], ans[1])

java

import java.util.*;

public class Main {

    static class Edge {
        int to, dist, cost;

        public Edge(int to, int dist, int cost) {
            this.to = to;
            this.dist = dist;
            this.cost = cost;
        }
    }

    static boolean lower(int[] x, int[] y) {
        // 比较两个 pair (距离, 花费)，距离小的优先，距离相同则比较花费
        return x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]);
    }

    static int n, m;
    static char[] city_type;
    static List<List<Edge>> graph = new ArrayList<>();
    static List<int[]> trans_edge = new ArrayList<>(); // 存储跨城市的边

    static int[][] dijkstra(int start) {
        // 初始化距离数组，每个城市的距离和代价初始为无穷大
        int[][] distance = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            distance[i][0] = Integer.MAX_VALUE;
            distance[i][1] = Integer.MAX_VALUE;
        }
        distance[start][0] = 0;  // 起点的距离和代价为0
        distance[start][1] = 0;

        boolean[] visited = new boolean[n + 1];  // 记录每个节点是否已经访问过

        for (int i = 1; i <= n; i++) {
            // 找到当前未访问节点中距离最小的节点
            int[] min_distance = {Integer.MAX_VALUE, Integer.MAX_VALUE};
            int min_index = -1;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && lower(distance[j], min_distance)) {
                    min_distance = distance[j];
                    min_index = j;
                }
            }

            if (min_index == -1) break; // 所有节点都访问过，或者不可达
            visited[min_index] = true;  // 标记该节点为已访问

            // 更新与当前节点相邻的其他节点的距离
            for (Edge edge : graph.get(min_index)) {
                int to = edge.to, w = edge.dist, c = edge.cost;
                if (visited[to] || city_type[to] != city_type[min_index]) continue; // 不同国，跳过
                int[] new_distance = {distance[min_index][0] + w, distance[min_index][1] + c};
                if (lower(new_distance, distance[to])) {
                    distance[to] = new_distance;
                }
            }
        }
        return distance;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        city_type = new char[n + 1];

        // 读取城市所属国家
        String cityTypeInput = sc.next();
        for (int i = 1; i <= n; i++) {
            city_type[i] = cityTypeInput.charAt(i - 1);
        }

        // 初始化图
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 读取所有边的信息
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a).add(new Edge(b, w, c));
            graph.get(b).add(new Edge(a, w, c));

            // 如果 a 和 b 属于不同的国家，记录这条跨城市的边
            if (city_type[a] != city_type[b]) {
                trans_edge.add(new int[]{a, b, w, c});
                trans_edge.add(new int[]{b, a, w, c});
            }
        }

        // 计算从城市 1 和 n 出发的最短路径
        int[][] distance_1 = dijkstra(1);
        int[][] distance_n = dijkstra(n);

        // 初始化答案
        int[] ans = {Integer.MAX_VALUE, Integer.MAX_VALUE};

        // 遍历所有跨城市的边，更新最短路径
        for (int[] edge : trans_edge) {
            int a = edge[0], b = edge[1], w = edge[2], c = edge[3];
            if (distance_1[a][0] == Integer.MAX_VALUE || distance_n[b][0] == Integer.MAX_VALUE) continue; // 不可达
            int[] new_ans = {distance_1[a][0] + distance_n[b][0] + w, distance_1[a][1] + distance_n[b][1] + c};
            if (lower(new_ans, ans)) {
                ans = new_ans;
            }
        }

        // 输出结果
        if (ans[0] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans[0] + " " + ans[1]);
        }
    }
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

$A$ 国与 $B$ 国是相邻的两个国家，每个国家都有很多城市，国家内部有很多连接城市的公路，国家之间也有很多跨国公路，连接两个国家的边界城市。

两个国家一共有 $N$ 个城市，编号 $1$ 到 $N$ ，一共有 $M$ 条公路，包括国内公路与跨国公路。

小明生活在 $A$ 国的城市 $1$（即编号为$1$的城市），想去 $B$ 国的城市 $N$ 游玩，由于小明办理的只能入境一次的签证，所以从城市 $1$ 到城市 $N$ 的路径中，只能通过一条跨国公路。

每条公路都一个距离，并且通过这条公路会有一个花费。

请帮小明计算出城市 $1$ 到城市 $N$ 的最短距离，并在距离最短的前提下，再计算出最少花费。

如果无法到达城市 $N$ ，输出 $-1$ 。

输入描述

1. 第一行是一个整数 $N$，表示两个国家的城市数量。
2. 第二行是一个整数 $M$，表示两个国家的公路数量，包括国内公路与跨国公路。
3. 第三行是一个长度为 $N$ 的字符串，字符串第 $i$ 个（从$1$开始计数）字符为 $A$ 或 $B$，表示城市 $i$ 属于 A 国或 B 国，其中第 $1$ 个字符一定为 $A$，第 $N$ 个字符一定为 $B$。
4. 最后是 $M$ 行，每行包含 $4$ 个整数 $U、V、W、C$，表示编号为 $U$ 的城市与编号为 $V$ 的城市之间有一条公路，长度是 $W$，花费是 $C$。

• 注意：所有公路都是双向的，且两个城市之间最多只有一条公路。

数据范围

$2≤N≤1000$，

$0≤M≤50000$，

$1≤U,V≤N$，

$1≤W≤500$。

输出描述

输出从城市$1$到城市$N$的最短距离，并在距离最短的前提下，再输出最少花费。 如果无法到达城市$N$，输出$-1$。

样例1

输入

5
5
AABBB
3 1 200 1
2 3 150 3
5 2 160 5
4 3 170 7
4 5 170 9

输出

540 17

说明

可以找到一条最优线路：城市1(A国) -> 城市3(B国) -> 城市4(B国) -> 城市5(B国)，

而且只通过一条跨国公路：城市1->城市3，

距离=200+170+170=540

花费=1+7+9=17

样例2

输入

6
7
AAABBB
1 2 150 2
1 3 100 2
1 4 160 1
2 6 150 5
3 5 100 3
4 6 160 1
5 6 100 4

输出

300 7

说明

可以找到一条最优线路：城市1(A国) -> 城市2(B国) -> 城市6(B国) ，

而且只通过一条跨国公路：城市1->城市2，

距离=150+150=300

花费=2+5=7

另外一条线路：1->3->5->6虽然距离也是300，

但是花费是2+3+4=9>7，所有不是最优线路

样例3

输入

4
3
ABAB
1 2 100 2
2 3 40 3
3 4 50 6

输出

-1