Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
#include
using namespace std; void Dijkstra_vu(vector
>> graph, int v_start, int u_end); // Ввод графа из файла. void test(string filename) { ifstream fin(filename); vector
>> graph; int N = 0; // Количество аэропортов. float D = 0.0f; // Максимальное расстояние без посадки. int A = 0; // Где я есть. int B = 0; // Куда мне надо. fin >> N; fin >> D; fin >> A; fin >> B; graph.resize(N); int grad1 = 0, grad2 = 0; float rad = 3.1415927f / 180.0f; vector
> coordinates; for (int i = 0; i < N; i++) { fin >> grad1; fin >> grad2; coordinates.push_back({ grad1 * rad, grad2 * rad }); } for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Расстояние между i и j портами. float dbtw = 2.0f * asin(sqrt(pow((sin((coordinates[i].first - coordinates[j].first) / 2.0f)), 2) + cos(coordinates[i].first) * cos(coordinates[j].first) * pow((sin((coordinates[i].second - coordinates[j].second) / 2.0f)), 2))); if (dbtw <= D || dbtw < 1e-7f) { graph[i].push_back({ dbtw, j }); graph[j].push_back({ dbtw, i }); } } } Dijkstra_vu(graph, A - 1, B - 1); } // Поиск кратчайшего пути между двумя вершинами. void Dijkstra_vu(vector
>> graph, int A, int B) { vector
d(graph.size(), FLT_MAX); // Кратчайшие расстояния до вершины. priority_queue
, vector
>, greater
>> Q; vector
isUsed(graph.size(), false); // Множество вершин, для которых вычислены кратчайшие пути из начальной. d[A] = 0.0f; Q.push({ 0.0f, A }); // { Расстояние, Номер_вершины }. while (!Q.empty()) { auto v_min = Q.top(); // Взята ближайшая вершина. Q.pop(); int v = v_min.second; // Номер вершины v. if (isUsed[v]) continue; isUsed[v] = true; // Для каждой вершины u, смежной с v: for (pair
e : graph[v]) { int u = e.second; // Номер вершины u. float len_vu = e.first; // Вес ребра со смежной. // Добавление в очередь вершины u, смежной с v. if (d[u] > d[v] + len_vu) { d[u] = d[v] + len_vu; Q.push({ len_vu, u }); } } if (isUsed[B]) { cout << fixed; cout.precision(3); cout << d[B] << endl; break; } } if (!isUsed[B]) cout << -1 << endl; } void main() { vector
in { "input01.txt", "input02.txt", "input03.txt", "input04.txt", "input05.txt", "input06.txt", "input07.txt", "input08.txt", "input09.txt", "input10.txt", "input11.txt", "input12.txt", "input13.txt", "input14.txt", "input15.txt", "input16.txt", "input17.txt", "input18.txt", "input19.txt", "input20.txt", "input21.txt", "input22.txt", "input23.txt", "input24.txt", "input25.txt", "input26.txt", "input27.txt", "input28.txt", "input29.txt", "input30.txt", "input31.txt", "input32.txt", }; vector
out { "output01.txt", // 1.571 "output02.txt", // -1 "output03.txt", // 3.142 "output04.txt", // 0.000 "output05.txt", // -1 "output06.txt", // 0.017 "output07.txt", // 0.000 "output08.txt", // -1 "output09.txt", // -1 "output10.txt", // -1 "output11.txt", // 0.868 "output12.txt", // 2.653 "output13.txt", // -1 "output14.txt", // -1 "output15.txt", // -1 "output16.txt", // 3.011 "output17.txt", // -1 "output18.txt", // -1 "output19.txt", // -1 "output20.txt", // 1.957 "output21.txt", // -1 "output22.txt", // -1 "output23.txt", // 2.484 "output24.txt", // 1.346 "output25.txt", // -1 "output26.txt", // 2.915 "output27.txt", // 0.933 "output28.txt", // 2.739 "output29.txt", // -1 "output30.txt", // 2.435 "output31.txt", // 1.668 "output32.txt", // 0.833 }; for (auto &obj : in) test(obj); int y; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)