后面更新

#include<bits/stdc++.h>
using PII = std::pair<int, int>;
const int N = 26 * 26;

const double eps = 1e-6;

double dis[N];
bool vis[N];
std::vector<PII> adj[N];

int hash(char a, char b)
{
    return (a - 'a') * 26 + (b - 'a');
}

// dfs优化spfa 适合判环 O(m)（m是边） 
// 判正环要找最长路
bool dfs(int u, double ans)
{
    vis[u] = true;
    for (auto [v, w] : adj[u])
    {
        if (dis[v]  < dis[u] - ans + w)
        {
            dis[v] = dis[u] - ans + w;
            if (vis[v] || dfs(v, ans))
                return true;
        }
    }
    vis[u] = false;
    return false;
}

bool check(double ans)
{
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    for (int i = 0; i < N; i++)
        if (dfs(i, ans))
            return true;
    return false;
}

// 最大
// (dis1 + dis2 + dis3 + ... + disk) / k >= ans
// 
// 
// (dis1 + dis2 + dis3 + ... + disk) >= ans * k
// 
// dis1-ans + dis2-ans +dis3-ans + ... + disk-ans >= 0 边权都减ans 判是否存在正环



int main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    while (std::cin >> n, n != 0)
    {
        for (int i = 0; i < N; i++)
            adj[i].clear();
        for (int i = 1; i <= n; i++)
        {
            std::string s;
            std::cin >> s;
            if (s.size() < 2)
                continue;
            int len = s.size();
            int u = hash(s[0], s[1]);
            int v = hash(s[len - 2], s[len - 1]);
            adj[u].push_back({v, len});
        }

        double l = 0, r = 1000;

        while (r - l > eps)
        {
            double mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }

        if (l == 0)
            std::cout << "No solution." << '\n';
        else
            std::cout << l << '\n';
    }




    return 0;
}