QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#183792 | #7184. Transport Pluses | winglessHussar | WA | 1ms | 3816kb | C++14 | 2.2kb | 2023-09-19 20:57:08 | 2023-09-19 20:57:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); ++ i)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>
#ifdef LOC
template<typename Stream, typename T1, typename T2>
Stream& operator << (Stream& out, pair<T1, T2> a) {return out << "(" << a.st << ", " << a.nd << ")";}
template<typename Stream, typename T>
Stream &operator << (Stream& out, T v) {
out << "{";
int i = 0;
for (auto x : v)
out << x << ((++ i) != sz(v) ? ", " : "");
return out << "}";
}
template<typename... Args>
void dump(Args... x) {((cerr << x << ", "), ...) << '\n';}
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif
using ll = long long;
long double eDist(long double x, long double y){
return sqrt(x * x + y * y);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, t; cin>>n>>t;
vector<pair<int, int>> points(n+2);
for(int i = 0;i <=n + 1; i++)cin>>points[i].first>>points[i].second;
vector<vector<pair<int, int>>> g(n+2);
for(int i = 2; i < n+2; i++){
int d = min(abs(points[0].first - points[i].first), abs(points[0].second - points[i].second)) + t;
g[0].push_back({i, d});
d = min(abs(points[1].first - points[i].first), abs(points[1].second - points[i].second));
g[i].push_back({1, d});
}
for(int i = 2; i < n+2; i++){
for(int j = i +1; j < n+2; j++){
int d = min(abs(points[i].first - points[j].first), abs(points[i].second - points[j].second)) + t;
g[i].push_back({j, d});
g[j].push_back({i, d});
}
}
vector<int> dist(n+2, 1e9);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
dist[0] = 0;
q.push({0, 0});
while(! q.empty()){
int d = q.top().first; int v = q.top().second; q.pop();
if(d == dist[v]){
for(auto p : g[v]){
if(d + p.second < dist[p.first]){
dist[p.first] = d + p.second;
q.push({dist[p.first], p.first});
}
}
}
}
cout<<fixed<<setprecision(5)<<min((long double)1.0 * dist[1], eDist(points[0].first - points[1].first, points[0].second - points[1].second))<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
input:
1 2 1 1 5 3 6 2
output:
4.00000
result:
wrong output format Unexpected end of file - int32 expected