题目链接 

思路： 其实本题就是给你一些假设的最短路，问这些最短路是否可以被进一步变短。

一开始没有去考虑到，已经成为最短路的点可以去松弛其他的点。

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>using namespace std; const int N = 1e5+10; 
const long long inf = 1e18; 
struct node {long long dis; int index;node(int x,long long y ) {index = x; dis = y ;}bool operator < (const node &a) const {return dis>a.dis; }
};
struct Edge{int to; long long dis; 
};
Edge edge[N*6]; 
bool vis[N];
long long dis[N];
priority_queue<node> que; 
int n,m,k; 
int head[N]; 
int nex[6*N];
int cnt=0; 
bool flag[N]; void add(int x,int y,long long w )  {edge[cnt].to = y; edge[cnt].dis = w; nex[cnt] = head[x]; head[x] = cnt; ++cnt; edge[cnt].to = x; edge[cnt].dis = w; nex[cnt] = head[y]; head[y] = cnt; ++cnt; 
}
int main()
{int a,b; int count = 0;int tx;long long w;   node temp(0,0); cin>>n>>m>>k;memset( head,-1,sizeof(head) );memset( vis,false,sizeof(vis) ); for ( int i=1; i<=n;i++ ) dis[i] = inf;  for ( int i=0; i<m; i++ ) {scanf("%d%d",&a,&b); cin>>w;add( a,b,w );  }for ( int i=0; i<k; i++ ) {scanf("%d",&a);cin>>w;  flag[a] = true ; if ( dis[a]==inf ) dis[a] = w; else {count++; if ( w<dis[a] ) dis[a] = w; }}  for ( int i=1; i<=n; i++ ) {if ( dis[i]!=inf ) {que.push(node(i,dis[i])); }}dis[1] = 0; que.push(node(1,0));  while( !que.empty() ) { temp = que.top();  que.pop(); tx = temp.index; if ( vis[tx]==false ) {vis[tx] = 1 ; for ( int i=head[tx]; i!=-1 ; i=nex[i] ) {if ( dis[tx]+edge[i].dis <= dis[edge[i].to] ) {if ( flag[edge[i].to] ) {flag[edge[i].to]=0;++count;}dis[edge[i].to] = dis[tx]+edge[i].dis; que.push( node( edge[i].to , dis[edge[i].to]));}	} }	}cout<<count<<endl; return 0; 
}