如题。

#include <bits/stdc++.h>
using namespace std;
#define double long double
const int N = 1e5 + 5, M = 1 + 26 * 26;
const double inf = 1e14, eps = 1e-10;
int n, fir[N], nxt[N << 2], to[N << 2], cnt, dep[M + 5];
double eval[N << 2], dis[M + 5];
bool inq[M + 5];
inline void add(int u, int v, double w) {
	to[++cnt] = v;
	eval[cnt] = w;
	nxt[cnt] = fir[u];
	fir[u] = cnt;
}
inline int getid(char x, char y) {
	int ret = (x - 'a') * 26 + y - 'a' + 1;
	return ret;
}
string tos(int x) {
	string res;
	do {
		res += char(x % 26 + 'a'); x /= 26;
	} while(x);
	reverse(res.begin(), res.end());
	if(res.size() == 1) res = 'a' + res;
	return res + ' ';
}
inline bool spfa(double x) {
	memset(dep, 0, sizeof dep);
	for(int i = 0; i < M; i++) dis[i] = inf;
	queue<int> q;
	q.push(M), inq[M] = true, dis[M] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = false;
		for(int i = fir[u]; i; i = nxt[i]) {
			int v = to[i];
//			cout << tos(u) << tos(v) << eval[i] << '\n';
			if(dis[u] + eval[i] - x < dis[v]) {
				dis[v] = dis[u] + eval[i] - x;
				dep[v] = dep[u] + 1;
				if(dep[v] >= M) return true;
				if(!inq[v]) {
					inq[v] = true;
					q.push(v);
				}
			}
		}
	}
	return false;
}

signed main() {
	ios::sync_with_stdio(false);
	string str;
	while((cin >> n) && n) {
		memset(fir, 0, sizeof fir);
		cnt = 0;
		bool flg = false;
		for(int i = 1; i <= n; i++) {
			cin >> str;
			int len = str.size();
			if(len <= 1) continue;
			add(getid(str[0], str[1]), getid(str[len - 2], str[len - 1]), len * 1.0);
		}
		for(int i = 0; i < M; i++) add(M, i, 0.0);
		double ans = 0.0, l = 0.0, r = 1001;
		while(r - l >= eps) {
			double mid = (l + r) / 2.0;
			if(spfa(mid)) flg = true, ans = mid, r = mid - eps;
			else l = mid + eps;
		}
		if(flg == false) cout << "No Solution.\n";
		else cout << fixed << setprecision(8) << ans << '\n';
	}
	return 0;
}