50 lines
No EOL
1.1 KiB
C++
50 lines
No EOL
1.1 KiB
C++
#include <iostream>
|
|
|
|
using namespace std;
|
|
|
|
long long x[20005];
|
|
long long y[20005];
|
|
long long D[20005];
|
|
bool visited[20005];
|
|
|
|
int main() {
|
|
int n;
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) {
|
|
cin >> x[i] >> y[i];
|
|
}
|
|
int s, t;
|
|
cin >> s >> t;
|
|
long long INF = 1000000000000000000LL;
|
|
for (int i = 1; i <= n; i++) {
|
|
D[i] = INF;
|
|
visited[i] = false;
|
|
}
|
|
D[s] = 0;
|
|
for (int i = 1; i <= n; i++) {
|
|
int u = -1;
|
|
long long min_d = INF;
|
|
for (int j = 1; j <= n; j++) {
|
|
if (visited[j] == false && D[j] < min_d) {
|
|
min_d = D[j];
|
|
u = j;
|
|
}
|
|
}
|
|
if (u == -1 || u == t || D[u] == INF) {
|
|
break;
|
|
}
|
|
visited[u] = true;
|
|
for (int v = 1; v <= n; v++) {
|
|
if (visited[v] == false) {
|
|
long long dx = x[u] - x[v];
|
|
long long dy = y[u] - y[v];
|
|
long long cost = D[u] + dx * dx + dy * dy;
|
|
if (cost < D[v]) {
|
|
D[v] = cost;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
cout << D[t] << "\n";
|
|
return 0;
|
|
} |