链接：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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7 const int maxn=3005,inf=1e9; 8 int dis[maxn][maxn]; 9 vector<int> 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<status> 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<G[S.v].size();i++){ 24 if(!vis[G[S.v][i]]){ 25 Q.push(status(G[S.v][i],S.dis+1)); 26 dis[s][G[S.v][i]]=S.dis+1; 27 vis[G[S.v][i]]=true; 28 } 29 } 30 } 31 } 32 int main(){ 33 // freopen("e:\in.txt","r",stdin); 34 int a,b,ans=-1; 35 scanf("%d%d",&n,&m); 36 for(int i=1;i<=n;i++){ 37 for(int j=1;j<=n;j++){ 38 dis[i][j]=inf; 39 } 40 dis[i][i]=0; 41 } 42 for(int i=0;i<m;i++){ 43 scanf("%d%d",&a,&b); 44 dis[a][b]=1;dis[b][a]=1; 45 G[a].push_back(b); 46 G[b].push_back(a); 47 } 48 scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2); 49 for(int i=1;i<=n;i++)bfs(i); 50 for(int mid1=1;mid1<=n;mid1++){ 51 for(int mid2=1;mid2<=n;mid2++){ 52 if(dis[s1][mid1]+dis[mid1][mid2]+dis[mid2][t1]<=l1&& 53 dis[s2][mid1]+dis[mid1][mid2]+dis[mid2][t2]<=l2&& 54 m-dis[s1][mid1]-dis[s2][mid1]-dis[mid1][mid2]-dis[mid2][t1]-dis[mid2][t2]>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 ",ans); 64 return 0; 65 }