链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1444

分析：相当于说，求s1到t1和s2到t2的路径之和最小值，若两条路径有重复部分，只计算一次。考虑重合部分，相当于重合部分算一次，其它部分各算一次，可以O(n^2)枚举重合部分(u,v)，然后重合部分同向时用dis[s1][u]+dis[s2][u]+dis[u][v]+dis[v][t1]+dis[v][t2]更新答案，否则同理。需要先预处理任意两点最短路径，Floyd的话O(n^3)会T，注意到每条边长度都是1，所以可以O(n^2)bfs一下即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn=3005,inf=1e9; 8 int dis[maxn][maxn]; 9 vector
          
            G[maxn];10 int n,m,s1,s2,t1,t2,l1,l2;11 struct status{12 int v,dis;13 status(int v,int dis){ this->v=v;this->dis=dis;}14 };15 void bfs(int s){16 bool vis[maxn];17 memset(vis,0,sizeof(vis));18 queue
           
             Q;19 Q.push(status(s,0));vis[s]=true;20 dis[s][s]=0;21 while(!Q.empty()){22 status S=Q.front();Q.pop();23 for(int i=0;i
            
             ans)55 ans=m-dis[s1][mid1]-dis[s2][mid1]-dis[mid1][mid2]-dis[mid2][t1]-dis[mid2][t2];56 if(dis[s1][mid1]+dis[mid1][mid2]+dis[mid2][t1]<=l1&&57 dis[t2][mid1]+dis[mid1][mid2]+dis[mid2][s2]<=l2&&58 m-dis[s1][mid1]-dis[t2][mid1]-dis[mid1][mid2]-dis[mid2][t1]-dis[mid2][s2]>ans)59 ans=m-dis[s1][mid1]-dis[t2][mid1]-dis[mid1][mid2]-dis[mid2][t1]-dis[mid2][s2];60 }61 }62 if(dis[s1][t1]<=l1&&dis[s2][t2]<=l2&&m-dis[s1][t1]-dis[s2][t2]>ans)ans=m-dis[s1][t1]-dis[s2][t2];63 printf("%d\n",ans);64 return 0;65 }