首页 > 代码库 > Codeforces Round #257 (Div. 1) (Codeforces 449B)

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

2024-07-13 04:15:55   231人阅读

题意：给力一张无向图，有一些边是正常道路，有一些边是铁路，问最多能删除几条铁路使得所有点到首都（编号为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 = 0; i <= n; ++i)        d[i] = INF;    memset(bo, 0, sizeof(bo));    d[1] = 0;    int st = 0, ed = 0;    while (!q.empty())        q.pop();    info a;    a.va = 0;    a.id = 1;    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 != -1; 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, -1, sizeof(head));    ecnt = 0;    for (int i = 0; i < m; ++i) {        int x, y, z;        scanf("%d%d%d", &x, &y, &z);        addedge(x, y, z, 0);        addedge(y, x, z, 0);    }    for (int i = 0; i < k; ++i) {        int x, y;        scanf("%d%d", &x, &y);        addedge(1, x, y, 1);        addedge(x, 1, y, 1);    }}void solve() {    Dij();    int ans = k;    for (int i = 2; i <= n; ++i) {        int flag = 0, flag1 = 0;        for (int j = head[i]; j != -1; j = e[j].nx) {            int u = e[j].to;            if (d[u] + e[j].va == d[i]) {                if (e[j].flag == 1)                    flag = 1;                else                    flag1 = 1;            }        }        if (flag == 1 && flag1 == 0)            ans--;    }    printf("%d\n", ans);}int main() {    init();    solve();}
View Code


联系
我们