P5683 道路拆除

P5683 道路拆除题目让我们求出最多可以删除多少条边后首都和s1s1s1s2s2s2的最短路径分别不大于t1t1t1t2t2t2我们可以先建图之后从首都跑一遍最短路判断在没有删除边的情况下首都和这两个城市的最短距离是否合法.如果合法我们可以再从s1s1s1和s2s2s2再各跑一遍最短路(这是因为我们将边删除后原图一定会变成一棵树)于是我们可以枚举中间节点判断当以这个节点为中转点时距离是否合法当距离不合法我们直接跳过这个点否则我们就更新我们保留的边的最小值(因为要求删除边的最大值)#includeiostream#includecstring#includecstdio#includealgorithm#includequeueusingnamespacestd;constintN3e55;structNode{intto,next,w;}edge[N*2];inthead[N],cnt;intn,m;ints1,t1,s2,t2;intdis[N][3];// dis[i][0] 表示以首都为起点跑最短路// dis[i][1] 表示以 s1 为起点跑最短路// dis[i][2] 表示以 s2 为起点跑最短路boolvis[N];voidadd(intu,intv,intw){edge[cnt].tov;edge[cnt].ww;edge[cnt].nexthead[u];head[u]cnt;}voiddijkstra(ints,intopt){priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;for(inti1;in;i)dis[i][opt]0x3f3f3f3f;memset(vis,false,sizeofvis);dis[s][opt]0;q.push({dis[s][opt],s});while(!q.empty()){intuq.top().second;q.pop();if(vis[u])continue;vis[u]true;for(intihead[u];i;iedge[i].next){intvedge[i].to;if(dis[v][opt]dis[u][opt]edge[i].w){dis[v][opt]dis[u][opt]edge[i].w;q.push({dis[v][opt],v});}}}}intmain(){scanf(%d %d,n,m);for(inti1;im;i){intu,v;scanf(%d %d,u,v);add(u,v,1);add(v,u,1);}scanf(%d %d %d %d,s1,t1,s2,t2);dijkstra(1,0);dijkstra(s1,1);dijkstra(s2,2);intans0x3f3f3f3f;// 保留边数的最小值// 判断在不删除边的情况下最短距离是否合法if(dis[s1][0]t1||dis[s2][0]t2)returnprintf(-1\n),0;for(inti1;in;i){intx1dis[i][0]dis[i][1],x2dis[i][0]dis[i][2];// x1 表示以当前节点为中转点时首都和 s1 之间的最短路径// x2 表示以当前节点为中转点时首都和 s2 之间的最短路径if(x1t1||x2t2)continue;// 由于这张图的边权为一所以边权和就代表着经过了几条边// x1 x2 - dis[i][0] 表示当前点可行时可以保留的边的个数ansmin(ans,x1x2-dis[i][0]);}printf(%d\n,m-ans);return0;}