BFS计算任意两点间的距离，N方枚举重合路径的两端。
#include
using namespace std;const int MAXN=3030;struct node
{int x,step;
}now,son;vector vec[MAXN];
int mp[MAXN][MAXN];void bfs(int x)
{queue q;now.x=x;now.step=0;q.push(now);mp[x][x]=0;while(!q.empty()){now=q.front();q.pop();for(int i=0;il1||mp[s2][t2]>l2){printf("-1\n");continue;}ans=m-mp[s1][t1]-mp[s2][t2];for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(mp[s1][i]+mp[i][j]+mp[j][t1]<=l1&&mp[s2][i]+mp[i][j]+mp[j][t2]<=l2)ans=max(ans,m-mp[s1][i]-mp[s2][i]-mp[i][j]-mp[j][t1]-mp[j][t2]);if(mp[s1][i]+mp[i][j]+mp[j][t1]<=l1&&mp[s2][j]+mp[j][i]+mp[i][t2]<=l2)ans=max(ans,m-mp[s1][i]-mp[s2][j]-mp[i][j]-mp[j][t1]-mp[i][t2]);}}printf("%d\n",ans);}
}