求城门个数

/算法思想：①根据城市的半径从小到大排序。
//②将城市设为图的顶点，与最接近的外围城市的边设为1。
//③用迪杰斯特拉算法找出两个城市最短路径。
typedef struct city {
  int x;
  int y;
  int r;
  char name;
};
int Dijkstra(int v1,int v2, vector<vector<int>> graph,int n) {
  int i, j, k, min;
  vector<int> d(n,0);
  vector<bool>visit(n,false);
  for (int i = 0; i < n; i++) {
    d[i] = graph[v1][i];
  }
  visit[v1] = true;
  for (int i = 0; i < n; i++) {
    min = 1e9;
    for (int j = 0; j < n; j++) {
      if (d[j] < min && visit[j] == false) {
        min = d[j];
        k = j;
      }
    }
    visit[k] = true;
    for (int j = 0; j < n; j++) {
      if (d[k] + graph[k][j] < d[j]) {
        d[j] = d[k] + graph[k][j];
      }
    }
  }
  return d[v2];
}
bool comp(city a, city b) {
  return a.r < b.r;
}
void mindoor() {
  cout << "请输入城市个数" << endl;
  int n;//城市个数
  int x;
  int y;
  int r;
  char name;
  cin >> n;
  vector<city> citys;
  vector<vector<int>> graph(n,vector<int>(n,100));
  for (int i = 0; i < n; i++) {
    city c;
    cout << "请输入城市名称" << endl;
    cin >> name;
    c.name = name;
    cout << "请输入城市坐标"<<endl;
    cin >> x;
    cin >> y;
    c.x = x;
    c.y = y;
    cout << "请输入城市半径" << endl;
    cin >> r;
    c.r = r;
    citys.push_back(c);
  }
  sort(citys.begin(), citys.end(),comp);
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      int x1 = citys[i].x;
      int y1 = citys[i].y;
      int x2 = citys[j].x;
      int y2 = citys[j].y;
      int r1 = citys[i].r;
      int r2 = citys[j].r;
      int d = pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5);
      if (d < r2 - r1) {
        graph[i][j] = 1;
        graph[j][i] = 1;
        break;
      }
    }
  }
  cout << "输入查找城市" << endl;
  char c1;
  char c2;
  cin >>c1;
  cin >>c2;
  int v1 = 0;
  int v2 = 0;
  for (int i = 0; i < n;i++) {
    if (citys[i].name == c1) {
      v1 = i;
    }
  }
  for (int i = 0; i < n; i++) {
    if (citys[i].name == c2) {
      v2 = i;
    }
  }
  cout << endl;
  cout << "门个数为：" << Dijkstra(v1, v2, graph, n);
}
int main() {
  mindoor();
}