本文主要是介绍CodeForces 543B. Destroying Roads 多源Dijkstra+暴力枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://codeforces.com/problemset/problem/543/B
B. Destroying Roads
In some country there are exactly n cities and m bidirectional roads connecting the cities. Cities are numbered with integers from 1 to n. If cities a and b are connected by a road, then in an hour you can go along this road either from city a to city b, or from city b to city a. The road network is such that from any city you can get to any other one by moving along the roads.
You want to destroy the largest possible number of roads in the country so that the remaining roads would allow you to get from city s1to city t1 in at most l1 hours and get from city s2 to city t2 in at most l2 hours.
Determine what maximum number of roads you need to destroy in order to meet the condition of your plan. If it is impossible to reach the desired result, print -1.
Input
The first line contains two integers n, m (1 ≤ n ≤ 3000,
) — the number of cities and roads in the country, respectively.
Next m lines contain the descriptions of the roads as pairs of integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). It is guaranteed that the roads that are given in the description can transport you from any city to any other one. It is guaranteed that each pair of cities has at most one road between them.
The last two lines contains three integers each, s1, t1, l1 and s2, t2, l2, respectively (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n).
Output
Print a single number — the answer to the problem. If the it is impossible to meet the conditions, print -1.
Examples
input
5 4 1 2 2 3 3 4 4 5 1 3 2 3 5 2output
0input
5 4 1 2 2 3 3 4 4 5 1 3 2 2 4 2output
1input
5 4 1 2 2 3 3 4 4 5 1 3 2 3 5 1output
-1
//题目大意：给定n个点m条边的无向图(边权全为1)，让你去掉最多的边使得d(s1, t1) <= l1 && d(s2, t2) <= l2，若不能满足输出-1，反之输出可以去掉的最多边数。
使用Dijkstra,求出多源最短路径，然后暴力枚举重复的边，，，
求出最少的分别两个点的最短路径长度，因为单位长度为1，所以最后的边的数量减去长度，就是我们要摧毁的最大的边的数量
This is the code
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x3f3f3f3f //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
const int maxn=3005;
struct HeapNode //Dijkstra算法用到的优先队列的节点
{int d,u;HeapNode(){ }HeapNode(int d,int u):d(d),u(u) {}bool operator < (const HeapNode &rhs)const{return d > rhs.d;//注意这个地方是大于号}
};
struct Edge //边
{int from,to,dist;Edge(int f,int t,int d):from(f),to(t),dist(d) {}
};
struct Dijkstra
{int n,m; //点数和边数,编号都从0开始vector<Edge> edges; //边列表vector<int> G[maxn];//每个节点出发的边编号(从0开始编号)bool done[maxn]; //是否已永久标号int d[maxn][maxn]; //d[s][t]的最近距离int p[maxn]; //p[i]为从起点s到i的最短路中的最后一条边的编号void init(int n){this->n=n;this->m=0;for(int i=0; i<=n; i++)G[i].clear();//清空邻接表edges.clear(); //清空边列表}void AddEdge(int from,int to,int dist){//如果是无向图，每条无向边调用两次AddEdgeedges.push_back(Edge(from,to,dist) );G[from].push_back(m++);}void dijkstra(int s)//求s到所有点的距离{priority_queue<HeapNode> Q;for(int i=0; i<=n; i++)d[s][i]=INT_INF;d[s][s]=0;memset(done,0,sizeof(done));Q.push(HeapNode(0,s) );while(!Q.empty()){HeapNode x=Q.top();Q.pop();int u=x.u;if(done[u])continue;done[u]= true;for(int i=0; i<G[u].size(); i++){Edge& e= edges[G[u][i]];if(d[s][e.to]> d[s][u]+e.dist){d[s][e.to] = d[s][u]+e.dist;p[e.to] = G[u][i];Q.push(HeapNode(d[s][e.to],e.to) );//这个地方要与HeapNode 里面的数据对应起来}}}}
} DJ;
inline int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
int main()
{int n=read();int m=read();DJ.init(n);for(int i=1;i<=m;++i){int u=read();int v=read();DJ.AddEdge(u,v,1);DJ.AddEdge(v,u,1);}int s1=read();int t1=read();int l1=read();int s2=read();int t2=read();int l2=read();for(int i=1;i<=n;++i)//DJ.dijkstra(i);if(DJ.d[s1][t1]>l1 || DJ.d[s2][t2]>l2)//最短路不能满足{cout<<"-1"<<endl;return 0;}int ans=DJ.d[s1][t1]+=DJ.d[s2][t2];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(DJ.d[s1][i]+DJ.d[i][j]+DJ.d[j][t1]<=l1&&DJ.d[s2][i]+DJ.d[i][j]+DJ.d[j][t2]<=l2)//消除重复的路s1--t1 && s2--t2ans=min(ans,DJ.d[s1][i]+DJ.d[i][j]+DJ.d[j][t1]+DJ.d[s2][i]+DJ.d[j][t2]);if(DJ.d[s1][i]+DJ.d[i][j]+DJ.d[j][t1]<=l1&&DJ.d[t2][i]+DJ.d[i][j]+DJ.d[j][s2]<=l2)//s1--t1 && t2--s2ans=min(ans,DJ.d[s1][i]+DJ.d[i][j]+DJ.d[j][t1]+DJ.d[t2][i]+DJ.d[j][s2]);}}cout<<m-ans<<endl;//边数减去道路所需return 0;
}
这篇关于CodeForces 543B. Destroying Roads 多源Dijkstra+暴力枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
