题目简述
有一张边带权的无向图，边分成两种，第一种无特殊限制，第二种边有一个端点在 $1$ 号节点，问至多可以删多少条边可以使原图从 $1$ 到所有点的最短路长度不变。
分析
很容易注意到需要跑单源最短路，由于题目中要求的是使最短路不变的情况，所以考虑是否可以在最短路过程中 DP 转移下功夫，很明显需要优先从第一种边转移，于是在转移的过程中注意一下转移过去的值相等时如何更新即可，因为最短路的转移过程没有后效性，所以这样转移是正确的。
最后统计没有进行 DP 转移的边的数量即可。
代码实现
#include <iostream>
#include <cstdio>
#include <queue>
#define int long long
inline int read();
int fir[100005];
int nxt[800005];
int v[800005];
int w[800005];
int knd[800005];
int now=0;
bool vised[100005];
class node{
public:
int x,y;
node(int xx,int yy){
x=xx;
y=yy;
}
};
bool operator < (node a,node b){
return a.y>b.y;
}
std::priority_queue<node>qu;
int from[100005];
int dp[100005];
int used[800005];
void add(int xx,int yy,int zz,int kk){
now++;
knd[now]=kk;
v[now]=yy;
w[now]=zz;
nxt[now]=fir[xx];
fir[xx]=now;
return ;
}
signed main(){
#ifdef ONLINE_JUDGE
#else
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int n=read(),m,k;
m=read();
k=read();
for(int i=1;i<=n;i++){
fir[i]=-1;
dp[i]=0x3f3f3f3f3f3f3f3fll;
}
for(int i=1;i<=m;i++){
int xx=read(),yy,zz;
yy=read();
zz=read();
add(xx,yy,zz,0);
add(yy,xx,zz,0);
}
for(int i=1;i<=k;i++){
int s=read();
int y=read();
add(1,s,y,1);
add(s,1,y,1);
}
dp[1]=0;
qu.push(node(1,0));
while(qu.size()>0){
node noww=qu.top();
qu.pop();
int now=noww.x;
if(vised[now]){
continue;
}
vised[now]=1;
for(int i=fir[now];i!=-1;i=nxt[i]){
if(dp[now]+w[i]<dp[v[i]]){
dp[v[i]]=dp[now]+w[i];
used[from[v[i]]]=0;
used[i]=1;
from[v[i]]=i;
if(!vised[v[i]])
qu.push(node(v[i],dp[v[i]]));
}else if(dp[now]+w[i]==dp[v[i]]&&knd[from[v[i]]]==1){
used[from[v[i]]]=0;
used[i]=1;
from[v[i]]=i;
}
}
}
int ans=0;
for(int i=m*2+1;i<=m*2+k*2;i+=2){
if(!used[i]&&!used[i+1]){
ans++;
}
}
printf("%lld",ans);
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
c=='-'?f=-1:1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return f*x;
}
/*
Anything about this program:
Type:
Description:
Example:
1:
In:
Out:
More:
*/