Submission #58464473

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define DEBUG cout << "Passing [" << __FUNCTION__ << "] in LINE " << __LINE__ << endl
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5, INF = 1e18, mod = 1e9 + 7;
int n, S, T, x[15], y[15];
double ans = INF, f[(1 << 7)][7][2]; // f[i][j][k] 状态 i 上次到的线段 j 结束时左端点0 右端点1
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
}
signed main()
{
	// freopen("text.in", "r", stdin);
	// freopen("text.out", "w", stdout);

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> S >> T;
	for (int i = 1; i <= n; i++)
		cin >> x[i * 2 - 1] >> y[i * 2 - 1] >> x[i * 2] >> y[i * 2];
	for (int i = 1; i <= (1 << n); i++)
		for (int j = 0; j <= n; j++)
			f[i][j][0] = f[i][j][1] = INF;
	for (int i = 0; i < n; i++)
	{
		double t = dis(x[i * 2 + 1], y[i * 2 + 1], x[i * 2 + 2], y[i * 2 + 2]) * 1.0 / T;
		f[1 << i][i][0] = dis(0, 0, x[i * 2 + 2], y[i * 2 + 2]) * 1.0 / S + t;
		f[1 << i][i][1] = dis(0, 0, x[i * 2 + 1], y[i * 2 + 1]) * 1.0 / S + t;
	}
	for (int i = 1; i < (1 << n); i++)
	{
		for (int j = 0; j < n; j++) if (i & (1 << j))
		{
			for (int k = 0; k < n; k++) if ((i & (1 << k)) == 0)
			{
				double t = dis(x[k * 2 + 1], y[k * 2 + 1], x[k * 2 + 2], y[k * 2 + 2]) * 1.0 / T;
				f[i | (1 << k)][k][0] = min(f[i | (1 << k)][k][0], f[i][j][0] + dis(x[j * 2 + 1], y[j * 2 + 1], x[k * 2 + 2], y[k * 2 + 2]) * 1.0 / S + t);
				f[i | (1 << k)][k][0] = min(f[i | (1 << k)][k][0], f[i][j][1] + dis(x[j * 2 + 2], y[j * 2 + 2], x[k * 2 + 2], y[k * 2 + 2]) * 1.0 / S + t);
				f[i | (1 << k)][k][1] = min(f[i | (1 << k)][k][1], f[i][j][0] + dis(x[j * 2 + 1], y[j * 2 + 1], x[k * 2 + 1], y[k * 2 + 1]) * 1.0 / S + t);
				f[i | (1 << k)][k][1] = min(f[i | (1 << k)][k][1], f[i][j][1] + dis(x[j * 2 + 2], y[j * 2 + 2], x[k * 2 + 1], y[k * 2 + 1]) * 1.0 / S + t);
			}
		}
	}
	for (int i = 0; i < n; i++)
		ans = min(ans, min(f[(1 << n) - 1][i][0], f[(1 << n) - 1][i][1]));
	printf("%0.12f\n", ans);
	
	return 0;
}

Submission Info

Judge Result