1444 破坏道路
1444 破坏道路
题目来源： CodeForces 基准时间限制：1.5 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 
收藏 
关注
在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。
现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。
输出最多可以破坏的道路数目，如果没有解，请输出-1
Input
单组测试数据。 第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n*(n-1)/2) )。 接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。 输入保证是一个连通图。 最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。Output
输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。Input示例
5 4 1 2 2 3 3 4 4 5 1 3 2 3 5 2Output示例
0
题解：spfa求出所有两点之间的最短距离，再暴力枚举i,j找可重复边，dis[s1][i]+dis[i][j]+dis[j][e1]<=t1&&dis[s2][i]+dis[i][j]+dis[j][e2]<=t2或dis[s1][i]+dis[i][j]+dis[j][e1]<=t1&&dis[e2][i]+dis[i][j]+dis[j][s2]<=t2,
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=3005;
int n,m,s1,s2,e1,e2,t1,t2,dis[maxn][maxn];
bool vis[maxn];
vector e[maxn];
queue q;
void spfa(int num){while(!q.empty()) q.pop();for(int i=1;i<=n;i++) vis[i]=0;q.push(num),vis[num]=1,dis[num][num]=0;while(!q.empty()){int now=q.front();vis[now]=0;q.pop();for(int i=0;idis[num][now]+1){dis[num][e[now][i]]=dis[num][now]+1;if(!vis[e[now][i]]) q.push(e[now][i]),vis[e[now][i]]=1;}}return;
}
int solve(){int ans=dis[s1][e1]+dis[s2][e2];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(dis[s1][i]+dis[i][j]+dis[j][e1]<=t1&&dis[s2][i]+dis[i][j]+dis[j][e2]<=t2)ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][e1]+dis[s2][i]+dis[j][e2]);if(dis[s1][i]+dis[i][j]+dis[j][e1]<=t1&&dis[e2][i]+dis[i][j]+dis[j][s2]<=t2)ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][e1]+dis[e2][i]+dis[j][s2]);}return m-ans;
}
int main(){scanf("%d%d",&n,&m);memset(dis,inf,sizeof(dis));for(int u,v,i=0;it1||dis[s2][e2]>t2) printf("-1\n");else printf("%d\n",solve());
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！