結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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;}