题意：给力一张无向图，有一些边是正常道路，有一些边是铁路，问最多能删除几条铁路使得所有点到首都（编号为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 ", ans); } int main() { init(); solve(); }