|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e3 + 10;
|
|
|
const int M = 1e5 + 10;
|
|
|
const int U = 26 * 26;
|
|
|
|
|
|
int n;
|
|
|
int h[N], e[M], w[M], ne[M], idx;
|
|
|
double dist[N];
|
|
|
bool st[N]; // 如果当前这个点 u 可以松弛的点 v 是被访问过的，那么就说明一定存在负环。
|
|
|
char str[N]; // 黄海替换为string,结果执行时间由70ms--> 400ms!!!
|
|
|
|
|
|
const double eps = 1e-3;
|
|
|
|
|
|
void add(int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
bool dfs(int u, double mid) {
|
|
|
if (st[u]) return 1; // 如果又见u，说明有环
|
|
|
bool flag = 0; // 我的后代们是不是有环？
|
|
|
st[u] = 1; // u我出现过一次了~
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
// 更新最小值，判负环
|
|
|
if (dist[v] > dist[u] - w[i] + mid) {
|
|
|
dist[v] = dist[u] - w[i] + mid;
|
|
|
// 检查一下我的下一个节点j,它要是有负环检查到，我也汇报
|
|
|
flag = dfs(v, mid);
|
|
|
if (flag) break;
|
|
|
}
|
|
|
}
|
|
|
st[u] = 0; // 回溯
|
|
|
return flag;
|
|
|
}
|
|
|
|
|
|
bool check(double mid) {
|
|
|
memset(dist, 0, sizeof dist);
|
|
|
for (int i = 0; i < U; i++)
|
|
|
if (dfs(i, mid)) return 1;
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
void solve() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
idx = 0;
|
|
|
|
|
|
while (n--) {
|
|
|
scanf("%s", str);
|
|
|
int len = strlen(str);
|
|
|
if (len < 2) continue;
|
|
|
int a = (str[0] - 'a') * 26 + str[1] - 'a';
|
|
|
int b = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
|
|
|
add(a, b, len);
|
|
|
}
|
|
|
|
|
|
double l = 0, r = 1e3;
|
|
|
while (r - l > eps) {
|
|
|
double mid = (l + r) / 2;
|
|
|
if (check(mid))
|
|
|
l = mid;
|
|
|
else
|
|
|
r = mid;
|
|
|
}
|
|
|
if (l < eps)
|
|
|
puts("No solution");
|
|
|
else
|
|
|
printf("%.2lf\n", r);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 多组测试数组，喜欢单开一个solve()进行处理，确实看着舒服
|
|
|
while (scanf("%d", &n), n) solve();
|
|
|
return 0;
|
|
|
} |
