首页 > 代码库 > codeforces257 div2 D最短路条数
codeforces257 div2 D最短路条数
题意：
给一个无向图，总共有 n个点，m+k条边，给定点所连的k条边可以选择删除
问最多删除多少条可以保持该定点到其他点的最短路不变
题解：
从定点出发做单元最短路
首先如果定点到某个点的最短路小于 可删边的长度，则肯定可以删除
此外如果最短路与可删边长度相等，而且最短路条数大于1，肯定也可以删除
所以在做最短路的时候需要记录一下条数
//同时还会有重边，也要注意处理
ps...这题sxbk的把普通的spfa 都卡了。。加了slf优化才过，据说dij可以轻松过。。不过我没试2333
以后写spfa还是都写deque版的吧= =！
代码：
#include <stdio.h>#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int inf =1000000001;struct edge{ int from,to,w,next;}e[800010];int head[100010];int vis[100010];int dist[100010];int vi[100010];int hs[100010];int n,m,t;void add(int i,int j,int w){ e[t].from=i; e[t].to=j; e[t].w=w; e[t].next=head[i]; head[i]=t++; return ;}void spfa(int s){ deque <int> q; for(int i=1;i<=n;i++) dist[i]=inf; memset(vis,false,sizeof(vis)); q.push_back(s); dist[s]=0; while(!q.empty()) { int u=q.front(); q.pop_front(); vis[u]=false; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(dist[v]>=dist[u]+e[i].w) { dist[v]=dist[u]+e[i].w; if(dist[v]==hs[v]) vi[v]++; else if(dist[v]<hs[v]) vi[v]=2; if(!vis[v]) { vis[v]=true; if(!q.empty()&&dist[v]<dist[q.front()]) //spfa的slf优化 q.push_front(v); else q.push_back(v); } } } }}int main(){ int a,b,c,k; scanf("%d%d%d",&n,&m,&k); t=0; memset(head,-1,sizeof(head)); while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } int ans=0; while(k--) { scanf("%d%d",&b,&c); if(hs[b]==0) { hs[b]=c; add(1,b,c); add(b,1,c); } else //处理重边 { ans++; if(c<hs[b]) { hs[b]=c; add(1,b,c); add(b,1,c); } } } spfa(1); for(int i=2;i<=n;i++) { if(vi[i]>1) ans++; } printf("%d\n",ans); return 0;}
codeforces257 div2 D最短路条数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。