堆优化dijkstra,假设哪条铁路能够被更新,就把相应铁路删除。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef long long int LL; typedef pair<LL,int> pLI; typedef pair<int,LL> pIL; const int maxn=210000; const LL INF=1LL<<60; int n,m,k; vector<pIL> edge[maxn]; LL dist[maxn]; bool train[maxn]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<m;i++) { int u,v;LL x; //scanf("%d%d%lld",&u,&v,&x); scanf("%d%d%I64d",&u,&v,&x); u--; v--; edge[u].push_back(make_pair(v,x)); edge[v].push_back(make_pair(u,x)); } for(int i=0;i<=n;i++) { dist[i]=INF; train[i]=false; } dist[0]=0; for(int i=0;i<k;i++) { int s; LL y; //scanf("%d%lld",&s,&y); scanf("%d%I64d",&s,&y); s--; train[s]=true; dist[s]=min(dist[s],y); } priority_queue<pLI> heap; for(int i=0;i<n;i++) { if(dist[i]!=INF) { heap.push(make_pair(-dist[i],i)); } } while(heap.size()) { pLI temp=heap.top(); heap.pop(); LL D=-temp.first; int u=temp.second; if(dist[u]!=D) continue; for(int i=0,sz=edge[u].size();i<sz;i++) { int v=edge[u][i].first; LL len=edge[u][i].second; if(dist[v]>=dist[u]+len) { if(train[v]==true) { train[v]=false; } } if(dist[v]>dist[u]+len) { dist[v]=dist[u]+len; heap.push(make_pair(-dist[v],v)); } } } int ans=k; for(int i=0;i<n;i++) { ans-=train[i]; } printf("%d ",ans); return 0; }