51nod 1444 破坏道路

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);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！