题解：P11795 [JOI 2016 Final] 铁路票价 / Train Fare

· · 题解

因为是跟原图比较最短路，所以操作完的边是没用的，我们可以直接把操作边删掉，删的时候检查这条边在原图上是否可以用来更新最短路，即是否满足 dis_{x}=dis_{y}+1 ，如果一个点可以走出最短路的边全被删完了，那这个点到 1 的答案肯定会改变，同时，这个点剩下的所有边也不可能用来更新其他点的最短路了，所以要把剩下的边也全删掉，因为每条边仅能被删一次，所以时间复杂度是 O\left ( m \right ) 的。

#include<bits/stdc++.h>
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define vt vector<int>
#define ll long long
#define pp pair<ll,ll>
#define N 200010
#define ull unsigned long long
using namespace std;
const ll M=998244353;
const int inf=1e9;
void add(ll &x,ll y) { if((x+=y)>=M) x-=M; }
void add(ll &x,ll y,ll z) { x=(x+y*z%M)%M; }
ll qm(ll x,ll y) {
    ll res=1;
    for(;y;x=x*x%M,y/=2) if(y&1) res=res*x%M;
    return res;
}
int n,m,q,ans,dis[N],ct[N],vis[N],idx;
struct node{
    int x,y;
}e[N];
vector<node> a[N];
void add(int x,int y) {
    a[x].pb({y,++idx});a[y].pb({x,idx});
    e[idx]={x,y};
}
void sol(int x,int y,int id) {
    if(vis[id]) return ;
    vis[id]=1;
    if(dis[x]>dis[y]) swap(x,y);
    if(dis[x]+1==dis[y]) ct[y]--;
    if(!ct[y]) {
        ans++;
        for(int i=0;i<a[y].size();i++) sol(y,a[y][i].x,a[y][i].y);
    } 
}
void bfs() {
    queue<int> q;q.push(1);
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    while(q.size()) {
        int x=q.front();q.pop();
        for(int i=0;i<a[x].size();i++) {
            int v=a[x][i].x;
            if(dis[v]==dis[x]+1) ct[v]++;
            else if(dis[v]>dis[x]+1) dis[v]=dis[x]+1,ct[v]=1,q.push(v);
        }
    }
}
void solve() {
    cin>>n>>m>>q; int u,v;
    for(int i=1;i<=m;i++) { cin>>u>>v;add(u,v); }
    bfs();
    while(q--) {
        cin>>u;
        sol(e[u].x,e[u].y,u);printf("%d\n",ans);
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);int t=1;
    while(t--) { solve(); }
    return 0;
}