一、最短路
1.图论建图
建图
先根据数据范围，确定建邻接矩阵还是邻接表。然后复杂的题目，先分析样例，用好终极源点这个特殊技巧（特征，出现多源起点）
单源最短路板子
分析
这道题检查自己板子是否背熟，学到了——dijkstra起点可以随意设置，可求出这起点到其他点的最短路
代码
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
using namespace std;
const int N=1e5+10;
typedef pair<int,int>P;
int n,m,st1,ed,d[N];
vector<P>g[N];
bool st[N];
int dijkstra()
{
memset(d,0x3f,sizeof d);
priority_queue<P,vector<P>,greater<P>>q;
memset(st,0,sizeof st);//记得重置
q.push({0,st1});
d[st1]=0;
while(q.size())
{
auto t=q.top();q.pop();
int id=t.y;
if(st[id])continue;
st[id]=true;
for(auto &w:g[id])
{
if(d[w.y]>d[id]+w.x)
{
d[w.y]=d[id]+w.x;
q.push({d[w.y],w.y});
}
}
}
return d[ed];
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>st1>>ed;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({c,b});
g[b].push_back({c,a});
}
cout<<dijkstra();
return 0;
}
分析
图论问题快速get到题意，这里是从p个牧场中找一个到其余牛所在的牧场距离和最小，输出距离和。所以首先是枚举每个牧场，用dijkstra或者spfa来处理出这个牧场到其余牧场的距离，随后对用n头牛所在牧场编号，注意这道题是牧场之间的距离，而非牛之间的距离。还有是如果存在某个距离是极大值说明两点之间无最短路。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=1e5+10;
typedef pair<int,int>P;
vector<P>g[N];
int d[N],n,p,c,a[N];
bool st[N];
int spfa(int x)
{
memset(d,0x3f,sizeof d);
memset(st,false,sizeof st);
queue<P>q;
q.push({x,0});
st[x]=true;
d[x]=0;
while(q.size())
{
auto t=q.front();
q.pop();
int id=t.x;
st[id]=false;
for(auto &w:g[id])
{
if(d[w.x]>d[id]+w.y)
{
d[w.x]=d[id]+w.y;
if(!st[w.x])
{
q.push({w.x,d[w,x]});
st[w.x]=true;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
int j=a[i];
if(d[j]==0x3f3f3f3f)return 0x3f3f3f3f;//没法到达
ans+=d[j];//从p个牧场求到其余牛所在牧场的距离
}
return ans;//返回
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>p>>c;
for(int i=1;i<=n;i++)cin>>a[i];
while(c--)
{
int x,y,z;
cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
//求最小值
int ans=1e9;
for(int i=1;i<=p;i++)//从每个牧场开始
{
ans=min(ans,spfa(i));
}
cout<<ans;
return 0;
}
分析
这道题边权特殊，求的是最大路径，并且因为扣除手续费所以是“ ×（1-z%）”，这个最短路需要求乘积，所以比较和更新的时候用*
代码——待完善（我用堆优化dijkstra写错了）
这道题重新做一遍
朴素版
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, INF = 0x3f3f3f3f;
double dis[N];
double rate[N][N];
bool st[N];
int n, m, a, b;
void dijkstra() {
dis[a] = 1;
for (int i = 0; i < n - 1; i++) {
int t = -1;
for (int j = 1; j <= n; ++j) {
if (!st[j] && (t == -1 || dis[t] < dis[j]))
t = j;
}
st[t] = true;
for (int j = 1; j <= n; ++j) {
if (dis[j] < dis[t] * rate[t][j])
dis[j] = dis[t] * rate[t][j];
}
}
}
int main() {
cin.tie(0);
cin >> n >> m;
int x, y, z;
for (int i = 1; i <= m; ++i) {
cin >> x >> y >> z;
rate[x][y] = rate[y][x] = 1.0 * (100 - z) / 100;
}
cin >> a >> b;
dijkstra();
printf("%.8lf", 100 / dis[b]);
return 0;
}
最优乘车
这道题重新做一遍
分析
主要难在建图
1.使用getline(cin,s)读取一整行,因为不换行，所以多写一遍把前面的换行
2.按字符串流将整行字符串分开，
stringstream s(字符串)
while(s>>p)这里p就是分割出来的字符串
3.把换乘转换成求最短路的问题。对邻接矩阵，bfs求出最短路即可
分析
有限制的最短路（多了等级限制），还是老话，如何建图？分析样例往往是突破口，我们最终是想尽可能降低到1号点的边权，问题是不知道从哪个点开始好，这里我们引入终结源点（0号点），其到每个点的边权即为每个物品的原始价格，因此在跑最短路的时候记得枚举从0开始。然后处理限制，目的是1号点，所以一切以1号点为主，以1号的rank的左右各m作为边界，枚举n各物品，去找到1号点的最短路，符合边界的才去更新。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n,m,w[N][N],d[N],l[N];
bool st[N];
int dijkstra(int down)
{
int up=down+m;
memset(d,0x3f,sizeof d);
memset(st,false,sizeof st);
d[0]=0;
for(int i=0;i<=n;i++)
{
int t=-1;
for(int j=0;j<=n;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))
t=j;
st[t]=true;
//接下来的点的等级需要以1为界
for(int j=1;j<=n;j++)
if(l[j]>=down&&l[j]<=up)
d[j]=min(d[j],d[t]+w[t][j]);
}
return d[1];//1号点是终点
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>m>>n;
memset(w,0x3f,sizeof w);
for(int i=1;i<=n;i++)w[i][i]=0;//注意！！！
for(int i=1;i<=n;i++)
{
int p,cnt;
cin>>p>>l[i]>>cnt;
w[0][i]=min(w[0][i],p);
while(cnt--)
{
int id;
cin>>id>>p;
w[id][i]=min(w[id][i],p);
}
}
int ans=INF;
for(int i=l[1]-m;i<=l[1];i++)ans=min(ans,dijkstra(i));
cout<<ans;
return 0;
}
2.最短路结合其他
（1）最短路&&dfs
分析
一开始就以为是最短路的板子，敲了板子交上果不其然全wa了，再看才注意到拜访是一个路线下来的。先预处理出所有点的单源最短路，再去枚举每个点的全排列，求个最小值。
代码
//理解题意，这里并非1号点到其余各点的距离，最多一条公路说明没有重边
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
typedef pair<int,int>P;
int n,m,a[6],d[6][N];
vector<P>g[N];
bool st[N];
void dijkstra(int be,int d[])
{
memset(d,0x3f,N*4);
memset(st,false,sizeof st);
d[be]=0;
priority_queue<P,vector<P>,greater<P>>q;
q.push({0,be});
while(q.size())
{
auto t=q.top();
q.pop();
int id=t.y;
if(st[id])continue;
st[id]=true;
for(auto &w:g[id])
{
if(d[w.y]>d[id]+w.x)
{
d[w.y]=d[id]+w.x;
q.push({d[w.y],w.y});
}
}
}
}
//枚举顺序，第几个了，起点，距离
int dfs(int u,int be,int dis)
{
if(u==6)return dis;
int ans=INF;
for(int i=1;i<=5;i++)//枚举全排列
{
if(!st[i])
{
int ne=a[i];
st[i]=true;
ans=min(ans,dfs(u+1,i,dis+d[be][ne]));
st[i]=false;//回溯
}
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
a[0]=1;
for(int i=1;i<=5;i++)cin>>a[i];
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
g[x].push_back({z,y});
g[y].push_back({z,x});
}
//int ans=0;
for(int i=0;i<6;i++)dijkstra(a[i],d[i]);//传车站和这个点到其余各个点距离
memset(st,false,sizeof st);
cout<<dfs(1,0,0);
//cout<<ans;
return 0;
}
反思
暴搜真的很差
（2）最短路&&二分
分析
能免费修k条，肯定修最贵（最长）的k条路，答案是自费的路中最长的那一条，所以问题转化为[1,n]的所有路中第k+1长的路，（这道题有点困，过后再整理）
代码
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#define long long int
#define x first
#define y second
using namespace std;
const int N=1e5+10,M=0x3f3f3f3f;
typedef pair<int,int>P;
vector<P>g[N];
int d[N],n,m,k;
bool st[N];
bool spfa(int u)
{
memset(d,0x3f,sizeof d);
memset(st,false,sizeof st);
queue<P>q;
d[1]=0;
q.push({1,0});
st[1]=true;
int dis=0;
while(q.size())
{
auto t=q.front();
q.pop();
int id=t.x;
st[id]=false;
for(auto &w:g[id])
{
if(w.y>u)dis=d[id]+1;
else dis=d[id];
if(d[w.x]>dis)
{
d[w.x]=dis;
if(!st[w.x])
{
q.push({w.x,d[w.x]});
st[w.x]=true;
}
}
}
}
return d[n]<=k;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
int l=0,r=1e6;
int ans=-1;
while(l<=r)
{
int mid=l+(r-l)/2;
if(spfa(mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
（3）最短路&&拓扑排序
分析
复习了拓扑排序，分开连通块可以用dfs、bfs、并查集（后两个后面记得学）
void dfs(int u,int bid)
{
id[u]=bid;
block[bid].push_back(u);//每个bid是一个联通块
for(auto &w:g[u])
{
if(!id[w.y])dfs(w.y,bid);
}
}
for(int i=1;i<=n;i++)
{
if(!id[i])dfs(i,++cnt);
}
代码：
//道路与航线（最短路&&拓扑排序）
//正权，道路，双向；航线，单向，无环，有正有负
//若为拓扑图
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
//#define my(i,a,b) for(int i=(a);i<=(b);i++)
//#define you(i,a,b) for(int i=(a);i>=(b);i--)
#define x first
#define y second
using namespace std;
const int N=3e4+10,M=2e5+10,INF=0x3f3f3f3f;
typedef pair<int,int>P;
vector<int>block[M];
int n,r,p,s;
int h[N],e[M],ne[M],w[M],idx,bcnt;
int dist[N],id[N],din[N],st[N];
queue<int>q2;
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u,int bid)
{
id[u]=bid;//u点连通块编号
block[bid].push_back(u);//block是对应的连通块内的点
for(int i=h[u];i!=-1;i=ne[i])//遍历u点出点
{
int j=e[i];
if(!id[j])dfs(j,bid);//对于出点，没有编号的继续去搜，编号因为在一个连通块中
}
}
void dijkstra(int bid)
{
priority_queue<P,vector<P>,greater<P>>q1;
for(auto &u:block[bid])//将这个连通块均入堆
q1.push({dist[u],u});
while(q1.size())
{
auto t=q1.top().y;q1.pop();
if(st[t])continue;
st[t]=true;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(id[j]==id[t])q1.push({dist[j],j});
}
//说明这是连通块之间的有向边
if(id[j]!=id[t]&&--din[id[j]]==0)q2.push(id[j]);
}
}
}
void tuopu()
{
//重置
memset(dist,0x3f,sizeof dist);
dist[s]=0;
//bcnt为连通块个数
for(int i=1;i<=bcnt;i++)
if(!din[i])q2.push(i);
while(q2.size())
{
int t=q2.front();
q2.pop();
dijkstra(t);//拓扑下求最短路
}
}
int main()
{
//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
scanf("%d%d%d%d",&n,&r,&p,&s);
memset(h,-1,sizeof h);
memset(st,false,sizeof st);
while(r--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
//dfs连通块
for(int i=1;i<=n;i++)
{
if(!id[i])dfs(i,++bcnt);
}
//读入航线，拓扑
while(p--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
din[id[b]]++;//注意是对连通块来求入读
}
tuopu();
for(int i=1;i<=n;i++)
if(dist[i]>INF/2)puts("NO PATH");
else printf("%d\n",dist[i]);
return 0;
}
三、最短路拓展方法
（1）虚拟源点
题型特征：终点唯一，有多个源点，注意与floyd区分，因为这里是求最小值，而floyd是具体每个源点的值。
做法：一般选取0作为虚拟源点，将0与多源点连边，边权为0。
Buy a Ticket
分析
看数据范围最多跑一次最短路，可是有多个源，所以引入虚拟源点，将n个点的点权转化为源点到这n个点的边权（这一步真的很巧妙），剩下的就是注意建图是无向图，还有往返就是把边权扩展2倍。
代码
//这里一开始思路错了，应该是把边权扩大两倍，而不是输出双倍的最短路
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f;
typedef pair<int,int>P;
int n,m,p[N],d[N];
vector<P>g[N];
bool st[N];
void dijkstra()
{
priority_queue<P,vector<P>,greater<P>>q;
memset(d,0x3f,sizeof d);
d[0]=0;
q.push({0,0});
while(q.size())
{
auto t=q.top();
q.pop();
int id=t.y;
if(st[id])continue;
st[id]=true;
for(auto &w:g[id])
{
if(d[w.y]>d[id]+w.x)
{
d[w.y]=d[id]+w.x;
q.push({d[w.y],w.y});
}
}
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v,k;
cin>>u>>v>>k;
g[u].push_back({2*k,v});
g[v].push_back({2*k,u});//双向边吗
}
//点权转为边权
for(int i=1;i<=n;i++)
{
cin>>p[i];
g[0].push_back({p[i],i});
}
dijkstra();
for(int i=1;i<=n;i++)
{
cout<<d[i]<<' ';//细心！！！点权已经转换了
}
return 0;
}
（2）分层图+拆点
//分层图+拆点
//如果没有门，那就bfs最短步数问题
//引入st状态，dis(x,y,st)从（1，1）走到（n,m）的拥有st药匙状态的最小步数
//(x,y)这里有一些药匙，可全部拿起，（这个是捡药匙）st|key(存在一个)，d[x,y,st|key]=min(d[x,y,st|key],d[x,y,st])
//向四个方向走，（1）无门和墙（步数+1），这个是行走转移，d[a,b,st]=min(d[a,b,st],d[x,y,st]+1)向相邻的格子移动
//最短路求的时候用双端队列bfs
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=105,M=12;
typedef pair<int,int>P;
int n,m,p;
int g[N][N],key[N];
int dis[N][1<<M];
bool st[N][1<<M];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int get(int x,int y)
{
return (x-1)*m+y;
}
int bfs()
{
memset(dis,0x3f,sizeof dis);
int z=get(1,1),state=key[z];
queue<P>q;
dis[z][state]=0,st[z][state]=true;
q.push({z,state});
while(q.size())
{
auto t=q.front();
q.pop();
int z1=t.x,state=t.y;
if(z1==n*m)return dis[z1][state];
int x=(z1-1)/m+1,y=(z1-1)%m+1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m)continue;
int z2=get(a,b),s=key[z2],k=g[z1][z2];
if(k==0)continue;
if(k>=1&&!(state>>k&1))continue;
s|=state;
if(!st[z2][s])
{
dis[z2][s]=dis[z1][state]+1,st[z2][s]=true;
q.push({z2,s});
}
}
}
return -1;
}
int main()
{
cin>>n>>m>>p;
int k,s;
cin>>k;
memset(g,-1,sizeof g);
while(k--)
{
int x1,y1,x2,y2,k;
cin>>x1>>y1>>x2>>y2>>k;
int z1=get(x1,y1),z2=get(x2,y2);
g[z1][z2]=g[z2][z1]=k;
}
cin>>s;
while(s--)
{
int x,y,k;
cin>>x>>y>>k;
int z=get(x,y);
key[z]|=1<<k;
}
cout<<bfs()<<endl;
return 0;
}
//先过一下自己会的，再回过头来继续巩固。
(3)最短路计数
使用djikstra（因为是拓扑序），所以只要引入一个类似dp的数组对于每次求最短路的时候继承和累计即可。
最短路计数
//因为dijkstra直接符合拓扑序，所以直接使用不用dp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
//#define d lld
using namespace std;
const int N=1e6+10,M=1e5+3;
typedef pair<int,int>P;
vector<int>g[N];
int n,m,d[N],st[N],ans[N];
void dijkstra()
{
memset(d,0x3f,sizeof d);
d[1]=0;
ans[1]=1;
priority_queue<P,vector<P>,greater<P>>q;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
if(st[t.y])continue;
st[t.y]=true;
for(auto &w:g[t.y])
{
//并非最短路，继承
if(d[w]>d[t.y]+1)
{
d[w]=d[t.y]+1;
ans[w]=ans[t.y];
q.push({d[w],w});
}
//是最短路，累计次数
else if(d[w]==d[t.y]+1)
ans[w]=(ans[w]+ans[t.y])%M;
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
//printf("%d",n);
while(m--)
{
int a,b;
scanf("%lld%lld",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
dijkstra();
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
习题
打工赚钱
分析
题目是有点权，边权有0和负权边的，算法上pass掉dijkstra，用spfa。
1.将点权转为边权，因为这题要求最多挣多少，即最长路，那么建图的时候应该将边权处理为负，跑最短路，最终答案取相反。那这里点权为正，边权为负，用前者-后者取相反后，即边权-点权。
2.一直走下去，说明存在环，这里我不清楚是负环还是正环，反正套模板。
3.记得最终答案不存在环的话输出相反数
cnt[y]=cnt[x]+1
if(cnt[y]>=n) 存在环
都判断完后则不存在环
//刷图论题+复习dp
//粗心，负权用spfa！！！
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
typedef pair<int,int>P;
int d1,p,c,f,s;//s是起点
int d[N],cnt[N];
bool st[N];
vector<P>g[N];
//s到哪些城市可以赚更多的钱
/*void dijkstra(int s)
{
memset(d,0x3f,sizeof d);
d[s]=-d1;
priority_queue<P,vector<P>,greater<P>>q;
q.push({-d1,s});
while(q.size())
{
auto t=q.top();
q.pop();
int id=t.y;
if(st[id])continue;
st[id]=true;
for(auto &w:g[id])
{
if(d[w.y]>d[id]+w.x)
{
d[w.y]=d[id]+w.x;
q.push({d[w.y],w.y});
}
}
}
}*/
bool spfa(int s)
{
memset(d,0x3f,sizeof d);
d[s]=-d1;
queue<P>q;
q.push({s,-d1});
st[s]=true;
while(q.size())
{
auto t=q.front();
q.pop();
int id=t.x;
st[id]=false;
for(auto &w:g[id])
{
if(d[w.y]>d[id]+w.x)
{
d[w.y]=d[id]+w.x;
cnt[w.y]=cnt[id]+1;
if(cnt[w.y]>c)return false;
if(!st[w.y])
{
q.push({w.y,d[w.y]});
}
}
}
}
return true;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>d1>>p>>c>>f>>s;
//求最长路
while(p--)
{
int a,b;
cin>>a>>b;
g[a].push_back({0-d1,b});
}
while(f--)
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({c-d1,b});
}
//每个城市点权为d，起点是s，
bool f=spfa(s);
int ans=1e9;//果然跑个最短路即可
for(int i=1;i<=c;i++)
{
ans=min(ans,d[i]);
}
if(f)
cout<<-ans;
else
cout<<-1;
return 0;
}
赚钱
分析
这题我我套上上面那个模板（注意spfa时记得把起点初始化为负的距离），加上虚拟源点后wa了一个点，那么这题其实可以用floyd。
步骤
1.邻接矩阵初始化，不知为何200
2.建图，正的就用点权-边权
3.分别进行两次Floyd，两次暴力去找最长路，判断是否相等。相等则说明不存在环，否则存在环。
//floyd方法
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int d,p,c,f;
int g[310][310];
void floyd(){
for(int k=1;k<=c;k++){
for(int i=1;i<=c;i++){
for(int j=1;j<=c;j++){
g[i][j]=max(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
int find()
{
int x=0;
for(int i=1;i<=c;i++)
for(int j=1;j<=c;j++)
x=max(x,g[i][j]);
return x;
}
int main(){
cin>>d>>p>>c>>f;
memset(g,200,sizeof(g));
int x,y,z;
for(int i=1;i<=p;i++)
{
cin>>x>>y;
g[x][y]=d;
}
for(int i=1;i<=f;i++)
{
cin>>x>>y>>z;
g[x][y]=d-z;
}
floyd();
int ans1=find();
floyd();
int ans2=find();
if(ans1!=ans2) cout<<"orz"<<endl;
else cout<<ans1+d<<endl;
return 0;
}
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
const int N=700,M=1e5+10;
int n;
int h[N],e[M],w[M],ne[M],idx;
double dist[N];
int cnt[N];
bool st[N];
char s[1010];
void init()
{
memset(h,-1,sizeof h);
idx=0;
}
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void chongzhi()
{
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
//能否找到负环与距离无关无需清空
}
bool check(double mid)
{
chongzhi();
queue<int>q;
for(int i=0;i<676;i++)
{
q.push(i);
st[i]=true;
}
int res=0;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i]-mid)
{
dist[j]=dist[t]+w[i]-mid;
cnt[j]=cnt[t]+1;
//剪枝
if(++res>10000)return true;//经验值
if(cnt[j]>=N)return true;
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}
return false;
}
int main()
{
//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
while(~scanf("%d",&n))
{
// scanf("%d",&n);
if(n==0)break;
init();
for(int i=0;i<n;i++)
{
scanf("%s",s);
int len=strlen(s);
if(len>=2)
{
int a=(s[0]-'a')*26+s[1]-'a';
int b=(s[len-2]-'a')*26+s[len-1]-'a';
add(a,b,len);
}
}
if(!check(0))puts("No solution");//平均长度0都不行
else
{
double l=0,r=1000;
while(r-l>1e-4)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%lf",r);
}
}
return 0;
}
