本文主要是介绍Destroying Roads CodeForces - 544D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
看题解才懂..
首先可以肯定的是 除了两条最短路上的边 其余边都可以去掉
而这两条最短路上的边 是否可以合并某些道路 使距离仍在l1与l2范围内(合并后未必是最短路)
求任意两点最短路 暴力枚举任意两点 看合并后是否满足l1与l2的范围
注意对每一对枚举的点i与j 有四种情况 s1可以连到i或j s2也可以连到i或j
#include <bits/stdc++.h>
using namespace std;struct node1
{int v;int w;int next;
};struct node2
{bool friend operator < (node2 n1,node2 n2){return n1.w>n2.w;}int v;int w;
};node1 edge[1000000];
priority_queue <node2> que;
int dis[3010][3010];
int first[3010],book[3010];
int n,m,num;
int s1,t1,l1,s2,t2,l2;void addedge(int u,int v,int w)
{edge[num].v=v;edge[num].w=w;edge[num].next=first[u];first[u]=num++;return;
}void dijkstra()
{node2 cur,tem;int i,j,u,v,w;memset(dis,0x3f,sizeof(dis));for(i=1;i<=n;i++){while(!que.empty()) que.pop();memset(book,0,sizeof(book));tem.v=i,tem.w=0;que.push(tem);dis[i][i]=0;while(!que.empty()){cur=que.top();que.pop();u=cur.v;if(book[u]) continue;book[u]=1;for(j=first[u];j!=-1;j=edge[j].next){v=edge[j].v,w=edge[j].w;if(!book[v]&&dis[i][v]>dis[i][u]+w){dis[i][v]=dis[i][u]+w;tem.v=v,tem.w=dis[i][v];que.push(tem);}}}}return;
}int main()
{int i,j,u,v,ans;while(scanf("%d%d",&n,&m)!=EOF){memset(first,-1,sizeof(first));num=0;for(i=1;i<=m;i++){scanf("%d%d",&u,&v);addedge(u,v,1);addedge(v,u,1);}scanf("%d%d%d",&s1,&t1,&l1);scanf("%d%d%d",&s2,&t2,&l2);dijkstra();if(!(dis[s1][t1]<=l1&&dis[s2][t2]<=l2)){printf("-1\n");continue;}ans=dis[s1][t1]+dis[s2][t2];for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2){ans=min(ans,dis[s1][i]+dis[j][t1]+dis[s2][i]+dis[j][t2]+dis[i][j]);}if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[t2][i]+dis[i][j]+dis[j][s2]<=l2){ans=min(ans,dis[s1][i]+dis[j][t1]+dis[t2][i]+dis[j][s2]+dis[i][j]);}if(dis[t1][i]+dis[i][j]+dis[j][s1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2){ans=min(ans,dis[t1][i]+dis[j][s1]+dis[s2][i]+dis[j][t2]+dis[i][j]);}if(dis[t1][i]+dis[i][j]+dis[j][s1]<=l1&&dis[t2][i]+dis[i][j]+dis[j][s2]<=l2){ans=min(ans,dis[t1][i]+dis[j][s1]+dis[t2][i]+dis[j][s2]+dis[i][j]);}}}printf("%d\n",m-ans);}return 0;
}
这篇关于Destroying Roads CodeForces - 544D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
