rt，用的不是dfs优化

#include<bits/stdc++.h>
#define fi first
#define se second
#define eps 1e-6
using namespace std;
int n,dis2[100001];
double dis[100001];
string s[100001];
vector<pair<int,int> >G[100001];
queue<int>q;
bool spfa(double s){
    while(q.size()) q.pop();
    memset(dis,0,sizeof dis);
    memset(dis2,0,sizeof dis2);
    for(int i=0;i<=700;i++) q.push(i);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++){
            if(dis[G[u][i].se]<dis[u]+G[u][i].fi-s){
                dis[G[u][i].se]=dis[u]+G[u][i].fi-s;
                dis2[G[u][i].se]=dis2[u]+1;
                if(dis2[G[u][i].se]>=700) return 1;
                q.push(G[u][i].se);
            }
        }
    }
    return 0;
}
int main(){
    while(cin>>n&&n){
        for(int i=1;i<=700;i++) G[i].clear(); 
        for(int i=1;i<=n;i++){
            cin>>s[i];
            if(s[i].size()>=2){
                int c1=(int)(s[i][0]-'a')*26+(int)(s[i][1]-'a'),c2=(int)(s[i][s[i].size()-2]-'a')*26+(int)(s[i][s[i].size()-1]-'a');
                G[c1].push_back({s[i].size(),c2});
            }
        }
        if(!spfa(0)){
            cout<<"No solution"<<endl;
            continue;
        }
        double l=0.0,r=1000.0;
        while(r-l>eps){
            double mid=(l+r)/2.0;
            if(spfa(mid)) l=mid;
            else r=mid;
        }
        cout<<l<<endl;
    }
}