結果

問題 No.5007 Steiner Space Travel
ユーザー oshamashama
提出日時 2022-07-30 17:36:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 4,082 bytes
コンパイル時間 1,878 ms
実行使用メモリ 6,952 KB
スコア 4,521,707
最終ジャッジ日時 2022-07-30 17:36:35
合計ジャッジ時間 3,731 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
const long long alpha = 5;
typedef long long ll;
struct solve
{
ll N, M;
vector<pair<ll, ll>> planet_coordinate;
vector<pair<ll, ll>> station_coordinate;
vector<vector<ll>> m;
vector<ll> d;
vector<ll> last;
solve()
{
cin >> N >> M;
planet_coordinate.resize(N);
station_coordinate.resize(M);
m.resize(N + M, vector<ll>(N + M));
d.resize(N + M, 1e18);
last.resize(N + M, 1e18);
for (int i = 0; i < N; i++)
{
cin >> planet_coordinate.at(i).first >> planet_coordinate.at(i).second;
}
}
ll dist(pair<ll, ll> a, pair<ll, ll> b)
{
return ((a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second));
}
ll distance(int i, int j)
{
return dist((i < N ? planet_coordinate.at(i) : station_coordinate.at(i - N)),
(j < N ? planet_coordinate.at(j) : station_coordinate.at(j - N))) *
(i < N ? 1 : 5) *
(j < N ? 1 : 5);
}
ll get_shortest(int start, vector<bool> &used, queue<int> &q)
{
for (int i = 0; i < N + M; i++)
{
for (int j = 0; j < N + M; j++)
{
m.at(i).at(j) = distance(i, j);
}
}
priority_queue<pair<ll, ll>> pq;
d.resize(N + M, 1e18);
pq.push(make_pair(0, start));
ll Md = 1e18;
int ind = 0;
for (int i = 0; i < N + M; i++)
{
// cerr << "hoge" << d.at(i) << endl;
d.at(i) = 1e18;
}
d.at(start) = 0;
while (pq.size())
{
int now = pq.top().second;
pq.pop();
for (int i = 0; i < N + M; i++)
{
int next = i;
// cerr << "-----" << now << ' ' << next << endl;
// cerr << d.size() << endl;
// cerr << m.at(0).size() << endl;
// cerr << d.at(next) << endl;
if (d.at(next) > d.at(now) + m.at(now).at(next))
{
d.at(next) = d.at(now) + m.at(now).at(next);
last.at(next) = now;
// cout << "Md " << endl;
if (N <= next)
{
pq.push(make_pair(d.at(next), next));
}
else if (Md > d.at(next) &&
used.at(next) == false)
{
// cout << "/* code */" << endl;
Md = d.at(next);
ind = next;
}
}
}
}
// cout << ind << endl;
int next = ind;
if (ind != -1)
{
stack<int> s;
while (ind != start)
{
s.push(ind);
// cerr << "check " << ind << ' ' << last.at(ind) << endl;
ind = last.at(ind);
}
while (s.size())
{
q.push(s.top());
s.pop();
}
}
used.at(next) = true;
return next;
}
void print_ans()
{
queue<int> q;
q.push(0);
vector<bool> used(N + M, 0);
used.at(0) = true;
int start = 0;
for (int i = 0; i < N; i++)
{
start = get_shortest(start, used, q);
// cout << start << endl;
}
for (int i = 0; i < M; i++)
{
cout << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
}
cout << q.size() << endl;
while (q.size())
{
int now = q.front();
// cout << now << endl;
cout << 1 + now / N
<< ' '
<< now % N + 1
<< endl;
q.pop();
}
}
};
int main()
{
solve s;
s.print_ans();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0