QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183793#7184. Transport PluseswinglessHussarWA 0ms3576kbC++142.2kb2023-09-19 20:57:402023-09-19 20:57:40

Judging History

你现在查看的是最新测评结果

  • [2023-09-19 20:57:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3576kb
  • [2023-09-19 20:57:40]
  • 提交

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));
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3576kb

input:

1 2
1 1
5 3
6 2

output:

4.00000

result:

wrong output format Unexpected end of file - int32 expected