Codeforces Round #257 (Div. 1) (Codeforces 449B)

题意：给力一张无向图，有一些边是正常道路，有一些边是铁路，问最多能删除几条铁路使得所有点到首都（编号为1）的最短路长度不变。

思路：求不能删除的铁路数，总数减掉就是答案。先求出首都到所有点的最短路，求完最短路后，枚举除首都外所有点，如果这个点被更新的边中只有铁路，那么就有一条铁路不能删除。

注意：这里求最短路一开始用SPFA在第45个点TLE，最后换成带堆优化Dijkstra

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include <iostream>

#include<queue>

#define M 1000010

#define N 100050

#define LL __int64

#define INF (1000000000000000LL)

using namespace std;

struct node {

    int to, nx, va, flag;

} e[M];

int head[N], ecnt;

struct info {

    int id, va;

};

bool operator<(info a, info b) {

    return a.va > b.va;

}

priority_queue<info> q;

void addedge(int x, int y, int va, int flag) {

    e[ecnt].to = y;

    e[ecnt].va = va;

    e[ecnt].nx = head[x];

    e[ecnt].flag = flag;

    head[x] = ecnt++;

}

bool bo[N];

LL d[N];

int n, m, k;

void Dij() {

    for (int i = ; i <= n; ++i)

        d[i] = INF;

    memset(bo, , sizeof(bo));

    d[] = ;

    int st = , ed = ;

    while (!q.empty())

        q.pop();

    info a;

    a.va = ;

    a.id = ;

    q.push(a);

    while (!q.empty()) {

        a = q.top();

        q.pop();

        int now = a.id;

        if (bo[now])

            continue;

        bo[now] = true;

        for (int j = head[now]; j != -; j = e[j].nx) {

            int u = e[j].to;

            if (d[u] > d[now] + e[j].va) {

                d[u] = d[now] + e[j].va;

                a.id=u;

                a.va=d[u];

                q.push(a);

            }

        }

    }

}

void init() {

    scanf("%d%d%d", &n, &m, &k);

    memset(head, -, sizeof(head));

    ecnt = ;

    for (int i = ; i < m; ++i) {

        int x, y, z;

        scanf("%d%d%d", &x, &y, &z);

        addedge(x, y, z, );

        addedge(y, x, z, );

    }

    for (int i = ; i < k; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        addedge(, x, y, );

        addedge(x, , y, );

    }

}

void solve() {

    Dij();

    int ans = k;

    for (int i = ; i <= n; ++i) {

        int flag = , flag1 = ;

        for (int j = head[i]; j != -; j = e[j].nx) {

            int u = e[j].to;

            if (d[u] + e[j].va == d[i]) {

                if (e[j].flag == )

                    flag = ;

                else

                    flag1 = ;

            }

        }

        if (flag ==  && flag1 == )

            ans--;

    }

    printf("%d\n", ans);

}

int main() {

    init();

    solve();

}