根据题意，我们关心的只是一个字符串的开头两位和结尾两位，那可以将这两个字符映射成一个数(字符串hash的思想)，这样A串能与 B串相连就转换成了A‘点与B’点相连，也就是图论问题。
然后二分枚举答案，进行判断

#include<bits/stdc++.h>
using namespace std;
int n;
int len;
string t;
struct oppo {
    int to,s,next;
} rood[200005];
int head[10005],tot;
void add(int from,int to,int s) {
    rood[++tot].s=s;
    rood[tot].to=to;
    rood[tot].next=head[from];
    head[from]=tot;
}
stack< int > v;
bool f[10005];
double vis[10005];
int all[10005];
void ppp()
{
    memset(f,0,sizeof(f));
    memset(all,0,sizeof(all));
    memset(vis,128,sizeof(vis));
    while(v.size())
        v.pop();
    for(int i=0; i<=10005; i++) {
        if(head[i]) {
            v.push(i);
            f[i]=1;
            vis[i]=0;
        }
    }
}
bool check(double mid) {
    ppp();
    int alll=0;
    while(v.size()) {
        int lxl=v.top();
        f[lxl]=0;
        v.pop();
        for(int i=head[lxl]; i; i=rood[i].next) {
            if(vis[rood[i].to]<vis[lxl]+rood[i].s-mid) {
                vis[rood[i].to]=vis[lxl]+rood[i].s-mid;
                all[rood[i].to]=all[lxl]+1;
                if(++alll>4*n)//玄学优化
                    return 1;
                if(all[rood[i].to]>n)
                    return 1;
                if(!f[rood[i].to]) {
                    f[rood[i].to]=1;
                    v.push(rood[i].to);
                }
            }
        }
    }
    return 0;
}
int main() {
    while(1)
    {
        int MAX=0;
        tot=0;
        memset(head,0,sizeof(head));
        cin>>n;
        if(!n)
            return 0;
        for(int i=1; i<=n; i++) {
            cin>>t;
            len=t.length();
            MAX=max(MAX,len);
            t=' '+t;
            int a=(t[1]-'a')*100+t[2]-'a';//hash一波
            int b=(t[len-1]-'a')*100+t[len]-'a';
            add(a,b,len);
        }
        double l=0,r=1000,mid;
        if(!check(0))
        {
            puts("No solution");
            continue;
        }
        while(l+0.01<=r) {
            mid=(l+r)/2;
            if(check(mid))
                l=mid+0.01;
            else
                r=mid-0.01;
        }
        printf("%.2lf\n",r);
    }
    return 0;
}