题意 ：
给出n个节点，m条道路 ，k条铁路。
铁路都是从1号节点开始的，求为了减少费用，可以拆掉多少条铁路，且最短路径到任意一点的距离不变
思路：
先建立铁路，标记由铁路可以到达的城市以及最短距离，之后用道路进行spfa 。如果在spfa中，可以松弛某一点，或者刚好等，那么必定是通过道路抵达的，标记取消。
最终判断还有多少个标记，就是必须需要的铁路
long long 过得去 int TLE45
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn=3e5+5; vector <pair<int ,int > > E[maxn]; long long d[maxn]; int vis[maxn]; int inq[maxn]; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) d[i]=0x3f3f3f3f3f3f3f3f; for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(make_pair(v,w)); E[v].push_back(make_pair(u,w)); } queue<int> q; int s=1; d[s]=0,vis[s]=1; q.push(1); for(int i=0;i<k;i++) { int v,w; scanf("%d%d",&v,&w); if(d[v]>w){ d[v]=w; inq[v]=1; vis[v]=1; q.push(v); } } while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=0;i<E[u].size();i++) { int v=E[u][i].first; int w=E[u][i].second; if(d[v]>=d[u]+w) { d[v]=d[u]+w; inq[v]=0; if(!vis[v]) { vis[v]=1; q.push(v); } } } } int ans=0; for(int i=1;i<=n;i++) { if(inq[i]) { ans++; } } printf("%d\n",k-ans); return 0; }