CF449B Jzzhu and Cities

@Pelom  November 11, 2019

题意

$n$个点,$m$条带权边的无向图,另外还有$k$条特殊边,每条边连接$1$和$i$
问最多可以删除这$k$条边中的多少条,使得每个点到$1$的最短距离不变

数据范围:$1 \le n,k \le 10^5,1\le m \le 3\times 10^5$

题解

最短路计数,判断这几条边是否再最短路上或这几个点有没有别的最短路可以达到

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define mp make_pair
typedef pair<int,int> pii;
const int N=1e5+10;
int n,m,k,u,v,w;
int cnt,ans;
int head[N],to[N],y[N],dis[N],tot[N];
struct edge{
    int nxt,to,w;
} e[N<<3];
inline void add(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
inline void Dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    pq.push(mp(0,1));
    for(;!pq.empty();){
        int d=pq.top().first,u=pq.top().second;
        pq.pop();
        if(d!=dis[u])
            continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]==d+e[i].w)
                tot[v]++;
            if(dis[v]>d+e[i].w){
                tot[v]=1;
                dis[v]=d+e[i].w;
                pq.push(mp(dis[v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=k;i++){
        scanf("%d%d",&to[i],&y[i]);
        add(1,to[i],y[i]);
    }
    Dijkstra();
    for(int i=1;i<=k;i++){
        u=to[i];
        if(dis[u]<y[i])
            ans++;
        if(dis[u]==y[i] && tot[u]>1){
            ans++;
            tot[u]--;
        }
    }
    printf("%d",ans);
    return 0;
}

添加新评论