5 5 3 1 2 1 2 3 2 1 3 3 3 4 4 1 5 5 3 5 4 5 5 5
2
2 2 3 1 2 2 2 1 3 2 1 2 2 2 3
2

思路 :

剪完图后,记录一个最小边权的个数,如果从1到v的距离有多个,那么就可以考虑删除v

代码

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define int long long #define maxn 1100000 using namespace std ; struct dy{ int x , y , z , next ; }a[maxn] ; int head[maxn] , vis[maxn] , dis[maxn] ; int n , m ,k ; int U[maxn] , V[maxn] ,in[maxn] ; typedef pair<int,int>pa ; priority_queue<pa,vector<pa>,greater<pa> >q ; int t ; void add(int x , int y , int z) { a[++t].x = x ; a[t].y = y ; a[t].z = z ; a[t].next = head[x] ; head[x] = t ; } void dij(int s) { memset(dis,0x3f,sizeof(dis)) ; memset(vis,0,sizeof(vis)) ; dis[s] = 0 , vis[s] = 0 ; q.push(make_pair(dis[s],s)) ; while(!q.empty()) { int u = q.top().second ; q.pop() ; if(vis[u]) continue ; vis[u] = 1 ; for(int i = head[u] ; i ; i = a[i].next ) { int v = a[i].y ; if(dis[v] > dis[u] + a[i].z ) { dis[v] = dis[u] + a[i].z ; in[v] = 1 ; q.push(make_pair(dis[v],v)) ; }else if(dis[v] == dis[u] + a[i].z) { in[v] ++ ; } } } } signed main () { scanf("%lld%lld%lld",&n,&m,&k) ; while(m --) { int x , y , z ; scanf("%lld%lld%lld",&x,&y,&z) ; add(x,y,z) ; add(y,x,z) ; } for(int i = 1 ; i <= k ; i ++) { scanf("%lld%lld",&U[i],&V[i]) ; add(1,U[i],V[i]) ; add(U[i],1,V[i]) ; } dij(1) ;int ans = 0 ; for(int i = 1 ; i <= k ; i ++) { if(dis[U[i]] < V[i] ) ans ++ ; else { if(dis[U[i]] == V[i] && in[U[i]] > 1) ans ++ , in[U[i]] -- ; } } printf("%lld\n",ans) ; return 0 ; }