这是一道最短路的题，而且貌似有 SPFA 之死嫌疑。
SPFA 已死，Dijkstra 当道！
就这道题来说，先存好原图，再将这些特殊边读入。在读入过程中，做一下处理，将单源最短路取一个\(\min{dis[v],value}\) ,同时记录有多少条特殊边重复，并把这些点存起来，加入堆中。
这些重复的特殊边不起作用应当很好理解。
然后跑一遍 Dijkstra ，记录一下这些特殊边有多少个被 hank 掉（指被其他方式更换掉 TA 的最短路地位）。注意，这里不是增加答案数，而是记录下这个边是否被更替掉。（笔者曾因为这个调了不少时间 QAQ 。
在最短路中再加一个处理，因为我们只要确定这条边没用，那么对于这个点的最短路就无须连续更新，所以可以将堆顶跳出（亲测可以防止 MLE ）。
最后 for 一遍上面记录的点，如果连向这个点的特殊边被 hank 掉 那么就增加答案数。
因为用到堆优化 Dijkstra ，所以本人用了 pair 操作，不懂的出门右转不谢。（借用了某大佬的 pair 整理笔记，在这里 sto TA orz）
好的，下面是代码：
#include<bits/stdc .h>#define pi pair<int,int>#define mp make_pair#define F first#define S second#define re registerusing namespace std;int n,m,k,dis[100005],sum,ans;bool vis[100005],ud[600005];priority_queue< pi > q;vector<int> v;int h[100005],cnt;struct node {//链式前向星存边 int to,nxt,cost;} b[600005];void add(int x,int y,int z) {//加边操作 b[ cnt].nxt=h[x]; b[cnt].to=y; b[cnt].cost=z; h[x]=cnt;}inline int read() {//快读 int sum=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { sum=(sum<<3) (sum<<1) ch-'0'; ch=getchar(); } return sum*w;}int main() { n=read(); m=read(); k=read(); for(re int i=1; i<=m; i) { int a,b,c; a=read(); b=read(); c=read(); add(a,b,c); add(b,a,c); } memset(dis,0x3f,sizeof(dis)); for(re int i=1; i<=k; i) { int v,c; v=read(); c=read(); if(dis[v]!=0x3f3f3f3f) ans;//记录重复边 dis[v]=min(dis[v],c); } for(int i=1; i<=n; i ) { if(dis[i]!=0x3f3f3f3f) { v.push_back(i); q.push(mp(-dis[i],i)); } } dis[1]=0; vis[1]=1; q.push(mp(0,1)); while(q.size()) { pi u=q.top(); q.pop(); vis[u.S]=1; for(re int i=h[u.S]; i; i=b[i].nxt) { int v=b[i].to,cost=b[i].cost; if(dis[v]>=dis[u.S] cost) { dis[v]=dis[u.S] cost; ud[v]=1;//记录被hank掉的边 q.push(mp(-dis[v],v)); } } while(q.size()&&vis[q.top().S]) q.pop();//跳出堆顶操作 } for(re int i=0; i<v.size(); i ) { if(ud[v[i]]) ans;//二次更新答案数 } printf("%d",ans); return 0;}联系客服
