求助!样例都过不了
查看原帖
求助!样例都过不了
519573
Daniel_yao楼主2022/7/31 23:02
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

const int N = 1005;

int n, m, s, t, x[N], y[N];

double dist[N];

struct Node {
  int v;
  double w;
  bool operator < (const Node &x) const {
    return x.w < w;
  }
};

vector <Node> e[N];

bool st[N];

void dijkstra() {
  priority_queue <Node> q;
  memset(dist, 0x3f, sizeof dist);
  dist[s] = 0;
  q.push((Node){s, 0});
  while(!q.empty()) {
    Node t = q.top(); q.pop();
    int x = t.v;
    if(st[x]) continue;
    st[x] = 1;
    for (int i = 0; i < e[x].size(); i++) {
      int y = e[x][i].v, wi = e[x][i].w;
      if(dist[y] > dist[x] + wi){
        dist[y] = dist[x] + wi;
        q.push((Node) {y, dist[y]});
      }
    }
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int a, b; cin >> a >> b;
    double lon = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
    cout << lon << '\n';
    e[a].push_back((Node){b, lon});
    e[b].push_back((Node){a, lon});
  }
  cin >> s >> t;
  dijkstra();
  printf("%.2lf\n", dist[t]);
  return 0;
}

2022/7/31 23:02
加载中...