用给定城市的经纬度，利用经纬度计算城市之间的距离，要求用C++编程实现输入起点和终点，算法能给出最优路线。

这个问题可以分为两个部分来解决。第一部分是计算城市之间的距离，第二部分是求解最优路线。下面是一个简单的实现：

首先，我们需要一个函数来计算两个城市之间的距离。我们可以使用 Haversine 公式，它基于两个城市的经纬度计算它们之间的距离。下面是一个使用 Haversine 公式计算距离的函数：

#include <cmath>

constexpr double kEarthRadius = 6371.0;  // 地球半径，单位为千米

// 计算两个城市之间的距离
double Distance(double lat1, double lon1, double lat2, double lon2) {
  double dLat = (lat2 - lat1) * M_PI / 180.0;
  double dLon = (lon2 - lon1) * M_PI / 180.0;
  double lat1r = lat1 * M_PI / 180.0;
  double lat2r = lat2 * M_PI / 180.0;

  double a = std::sin(dLat / 2.0) * std::sin(dLat / 2.0) +
             std::sin(dLon / 2.0) * std::sin(dLon / 2.0) * std::cos(lat1r) *
                 std::cos(lat2r);
  double c = 2.0 * std::atan2(std::sqrt(a), std::sqrt(1.0 - a));
  return kEarthRadius * c;
}

接下来，我们需要一个数据结构来表示城市和它们之间的距离。我们可以使用邻接矩阵来实现。下面是一个简单的实现：

#include <iostream>
#include <vector>

// 城市结构体，包含经纬度和名称等信息
struct City {
  std::string name;
  double lat;
  double lon;
};

// 图结构体，表示城市之间的距离
struct Graph {
  std::vector<std::vector<double>> dist;  // 邻接矩阵，表示城市之间的距离
  std::vector<City> cities;               // 城市列表
};

// 在图中添加一个城市
void AddCity(Graph* graph, const City& city) {
  graph->cities.push_back(city);
  int n = graph->cities.size();
  graph->dist.resize(n);
  for (int i = 0; i < n; ++i) {
    graph->dist[i].resize(n);
    for (int j = 0; j < n; ++j) {
      if (i == j) {
        graph->dist[i][j] = 0.0;
      } else {
        graph->dist[i][j] = Distance(city.lat, city.lon, graph->cities[j].lat,
                                      graph->cities[j].lon);
      }
    }
  }
}

现在我们已经有了一个可以计算城市之间距离的函数和一个表示城市和它们之间距离的邻接矩阵。

接下来，我们需要一个算法来求解最优路线。这个问题可以转化为一个旅行商问题（TSP）。TSP 是一个经典的 NP 难问题，但是对于小规模的问题，我们可以使用动态规划来求解。

具体来说，我们可以使用一个二维数组 dp，其中 dp[i][j] 表示从起点出发，经过 i、j 两个城市，访问其它所有城市恰好一次后回到起点的最短距离。我们可以使用下面这个递推公式来更新 dp：

dp[S][i] = min{dp[S-{i,j}][j] + dist[i][j]}，其中 S 是表示访问其它城市的状态集合，S-{i,j} 表示去掉 i 和 j 后的状态集合。

最终的最优路线长度就是 dp[0][0]。

下面是一个简单的实现：

#include <algorithm>
#include <limits>

// 计算最优路线长度
double TSP(const Graph& graph) {
  int n = graph.cities.size();
  std::vector<std::vector<double>> dp(1 << n, std::vector<double>(n, -1.0));
  dp[(1 << n) - 1][0] = 0.0;
  for (int S = (1 << n) - 2; S >= 0; --S) {
    for (int i = 0; i < n; ++i) {
      if (!(S & (1 << i))) continue;
      for (int j = 0; j < n; ++j) {
        if (!(S & (1 << j))) continue;
        int S2 = S ^ (1 << i) ^ (1 << j);
        if (dp[S2][j] < 0.0) continue;
        double d = graph.dist[i][j];
        if (dp[S][i] < 0.0 || dp[S][i] > dp[S2][j] + d) {
          dp[S][i] = dp[S2][j] + d;
        }
      }
    }
  }
  return dp[0][0];
}

// 计算最优路线
std::vector<int> GetOptimalRoute(const Graph& graph) {
  int n = graph.cities.size();
  std::vector<std::vector<double>> dp(1 << n, std::vector<double>(n, -1.0));
  std::vector<std::vector<int>> parent(1 << n, std::vector<int>(n, -1));
  dp[(1 << n) - 1][0] = 0.0;
  for (int S = (1 << n) - 2; S >= 0; --S) {
    for (int i = 0; i < n; ++i) {
      if (!(S & (1 << i))) continue;
      for (int j = 0; j < n; ++j) {
        if (!(S & (1 << j))) continue;
        int S2 = S ^ (1 << i) ^ (1 << j);
        if (dp[S2][j] < 0.0) continue;
        double d = graph.dist[i][j];
        if (dp[S][i] < 0.0 || dp[S][i] > dp[S2][j] + d) {
          dp[S][i] = dp[S2][j] + d;
          parent[S][i] = j;
        }
      }
    }
  }
  std::vector<int> route;
  int S = 0, i = 0;
  while (route.size() < n) {
    route.push_back(i);
    int j = parent[S][i];
    S |= 1 << i;
    i = j;
  }
  return route;
}

最后，我们可以使用上述函数来求解最优路线并输出结果：

int main() {
  Graph graph;
  AddCity(&graph, {"Beijing", 39.9042, 116.4074});
  AddCity(&graph, {"Shanghai", 31.2304, 121.4737});
  AddCity(&graph, {"Guangzhou", 23.1291, 113.2644});
  AddCity(&graph, {"Shenzhen", 22.5431, 114.0579});
  AddCity(&graph, {"Chengdu", 30.5728, 104.0668});
  AddCity(&graph, {"Chongqing", 29.4316, 106.9123});

  double dist = TSP(graph);
  std::cout << "The optimal route length is " << dist << " km." << std::endl;

  std::vector<int> route = GetOptimalRoute(graph);
  std::cout << "The optimal route is: ";
  for (int i : route) {
    std::cout << graph.cities[i].name << " -> ";
  }
  std::cout << graph.cities[route[0]].name << std::endl;

  return 0;
}

以上是一个简单的实现，但是它的时间复杂度为 O(n^22^n)，对于大规模的问题来说，它是无法接受的。如果需要处理大规模的 TSP 问题，我们需要使用更高效的算法，例如分支定界法、遗传算法等。