分析

设 \(d(x)\) 为 \(1\) 到 \(x\) 的最短路径长度，\(cnt(x)\) 为最短路条数。

不难发现，对于一条特殊边 \((1 \rightarrow x)\)，边权为 \(w\)，它能被删除，当且仅当满足以下条件之一。

• \(w > d(x)\)
• \(w= d(x)\) 并且 \(cnt(x) > 1\)

所以直接在图上跑 Dijkstra，求出最短路及其数量，最后判断就好了。

没啥难度，但是好像会卡掉常规 SPFA。

顺带一提样例 2 里面，2 个点 5 条边，稠密图警告。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<ll,int>
#define mp make_pair
const int N=1e5+5, M=3e5+5;
int n, m, k, ans, u[N], v[N], cnt[N];
ll d[N];
int c, h[N], ver[M*4], nxt[M*4], w[M*4];
bool vis[N];
priority_queue<PII > q;
void add(int x,int y,int z) {
	ver[++c]=y, w[c]=z, nxt[c]=h[x], h[x]=c;
}
void dijkstra() {
	memset(d,0x3f,sizeof(d));
	d[1]=0, q.push(mp(0,1));
	while(q.size()) {
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=h[x];i;i=nxt[i]) {
			int y=ver[i], z=w[i];
			if(d[y]>d[x]+z) {
				d[y]=d[x]+z, cnt[y]=1;
                // 此时长度为d[x]+z的到达y的最短路只有1条
				q.push(mp(-d[y],y));
			}
			else if(d[y]==d[x]+z) ++cnt[y]; // 长度相等，另一条最短路。
		}
	}
}
signed main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y,z;i<=m;++i) {
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z), add(y,x,z);
	}
	for(int i=1;i<=k;++i) {
		scanf("%d%d",&u[i],&v[i]);
		add(1,u[i],v[i]), add(u[i],1,v[i]);
	}
	dijkstra();
	for(int i=1;i<=k;++i) {
		if(d[u[i]]<v[i]) ++ans; 
		else if(d[u[i]]==v[i]&&cnt[u[i]]>1) ++ans, --cnt[u[i]];
	}
	printf("%d\n",ans);
}