11987번: 鉄道運賃

https://www.acmicpc.net/problem/11987

#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAX_N = 1e5, MAX_M = 2e5;
int cst[MAX_N + 1], n, m, k, ind[MAX_N + 1], a[MAX_M + 1], b[MAX_M + 1], r;
vector<int> adj[MAX_N + 1];
queue<int> q;
set<pair<int, int> > st;
void dfs(int h) {
    if (ind[h]) return;
    for (auto it : adj[h])
        if (cst[h] + 1 == cst[it] && st.find({ h,it }) == st.end())st.insert({ h,it }), --ind[it], dfs(it);
    r++;
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", a + i, b + i);
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    cst[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int h = q.front();
        for (auto it : adj[h]) {
            if (!cst[it]) cst[it] = cst[h] + 1, q.push(it);
            if (cst[it] == cst[h] + 1) ind[it]++;
        }
        q.pop();
    }
    for (int i = 0, x; i < k; i++) {
        scanf("%d", &x);
        int ta = a[x], tb = b[x];
        if (cst[ta] > cst[tb]) swap(ta, tb);
        if (cst[ta] ^ cst[tb] && st.find({ ta,tb }) == st.end())st.insert({ ta,tb }), --ind[tb], dfs(tb);
        printf("%d\n", r);
    }
    return 0;
}