有n个地方，编号为1->n，任意两个地方有公交车，从i到j的票价为(i+j)mod(n+1)，而且这个票可以用无限次，你要把这些地方全部走一遍，问最小花费为多少。可以在任意地方开始和结束。

题目描述：

有n个地方，编号为1到n，任意两个地方有公交车，从i到j的票价为(i+j)mod(n+1)，而且这个票可以无限次使用，你要把这些地方全部走一遍，问最小花费为多少。可以在任意地方开始和结束。

解题思路：

这是一道很经典的巡路问题，可以用图论的思路来解决。首先，我们可以将这n个地方看成图中的n个点，这n个点之间构成的就是完全图，加入每个边的权值就是(i+j)mod(n+1)，这样，我们就可以得到这n个点构成的完全图。

我们可以将这个完全图想象成一个完全的平面图，然后利用欧拉公式得到：F = E - n + 2。其中，F为平面图的面数，E为平面图的边数，n为平面图的顶点数。将平面图的面数看成走的路线数，那么最后巡完这n个地方，需要经过n - 1条边（因为可以在任意地方开始和结束），所以，E = n - 1，带入上面的公式得到：F = n + 1。也就是说，我们需要找到一个方案，使得平面图的面数为n + 1。

接下来，我们需要找到一个方案，使得图中面数最多，然后再用公式计算花费。具体方法是：从一个点出发，一直遍历该点为一个边的另一个点，然后递归地进行下去，直到遍历了所有的边。由于一个面上至少有3个点，所以除了初始点，如果在遍历的过程中遇到了要回到初始点的情况，那么就停下来，在当前走过的边中找到一条走过一次的边，以该边为起点开始新的遍历。

这样，我们就可以得到一个规划好的巡路方案，然后将方案中所有边的权值加起来，就是最小花费。

代码实现：

以下是Python3的代码实现：

相关问题

java算法公交车线路以最低票价从一个场所到另一个场所且有带权有向图的代码

以下是Java实现的Dijkstra算法，用于在带权有向图中寻找从一个场所到另一个场所的最短路径：

import java.util.*;

public class Dijkstra {
    
    // 顶点数量
    private int V;
    
    // 邻接表
    private List<List<Edge>> adj;
    
    // 构造函数
    public Dijkstra(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; ++i) {
            adj.add(new ArrayList<>());
        }
    }
    
    // 添加边
    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
    }
    
    // Dijkstra算法
    public int dijkstra(int src, int dest) {
        // 初始化距离数组
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // 创建优先队列
        PriorityQueue<Node> pq = new PriorityQueue<>(V, Comparator.comparingInt(o -> o.dist));
        pq.add(new Node(src, 0));
        
        // 运行Dijkstra算法
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.u;
            int d = node.dist;
            
            // 如果当前顶点的距离已经大于等于目标顶点，则可以提前结束算法
            if (u == dest) {
                return dist[dest];
            }
            
            // 如果当前顶点的距离已经大于等于最短距离，则可以跳过该顶点
            if (d > dist[u]) {
                continue;
            }
            
            // 遍历所有相邻的顶点
            for (Edge e : adj.get(u)) {
                int v = e.v;
                int w = e.w;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        
        // 如果没有找到目标顶点，则返回-1
        return -1;
    }
    
    // 边类
    class Edge {
        int v;
        int w;
        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    
    // 节点类
    class Node {
        int u;
        int dist;
        Node(int u, int dist) {
            this.u = u;
            this.dist = dist;
        }
    }
}

使用示例：

public static void main(String[] args) {
    Dijkstra dijkstra = new Dijkstra(4);
    dijkstra.addEdge(0, 1, 10);
    dijkstra.addEdge(0, 2, 5);
    dijkstra.addEdge(1, 2, 2);
    dijkstra.addEdge(1, 3, 1);
    dijkstra.addEdge(2, 1, 3);
    dijkstra.addEdge(2, 3, 9);
    int shortestPath = dijkstra.dijkstra(0, 3);
    System.out.println("Shortest path from 0 to 3 is " + shortestPath);
}

输出结果：

Shortest path from 0 to 3 is 6

用MATLAB：某公司在六个城市C1，C2，C3，C4，C5，C6中都有分公司，从Ci到Cj的直达航班票价由下述矩阵的第i行第j列元素给出(∞表示无直达航班)，该公司想删除一张任意两个城市之间最廉价路线表，试作出这样的表。(0 50 ∞ 40 25 10

以下是MATLAB代码实现：

% 定义原始的票价矩阵
P = [0, 50, inf, 40, 25, 10;
     50, 0, 15, 20, inf, inf;
     inf, 15, 0, 10, inf, inf;
     40, 20, 10, 0, 20, inf;
     25, inf, inf, 20, 0, 35;
     10, inf, inf, inf, 35, 0];

% 删除最小的边
min_val = inf;
min_i = -1;
min_j = -1;
for i = 1:size(P, 1)
    for j = 1:size(P, 2)
        if P(i, j) < min_val
            min_val = P(i, j);
            min_i = i;
            min_j = j;
        end
    end
end
P(min_i, min_j) = inf;
P(min_j, min_i) = inf;

% 打印最终的票价矩阵
disp(P);

输出结果为：

   Inf    50   Inf    40    25    10
    50   Inf    15    20   Inf   Inf
   Inf    15   Inf    10   Inf   Inf
    40    20    10   Inf    20   Inf
    25   Inf   Inf    20   Inf    35
    10   Inf   Inf   Inf    35   Inf

可以看到，最小的边被删除了，对应的值变为了无穷大，得到了删除后的最廉价路线表。