C++14(g++5.4) 解法, 执行用时: 122ms, 内存消耗: 6460K, 提交时间: 2020-10-08 00:26:06

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <cmath>
using namespace std;
#define For(i, a, b) for(int i = (a), _ = (b); i <= _; i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define maxn 1000000
#define inf 0x7fffffff
int n, m , t;
struct edge{
	int to, dis, next;
}e[maxn];

struct zz{
	int dis, to, z;
}k[maxn];

struct node {
	int dis, pos;
	bool operator < (const node& x) const {
		return x.dis < dis;
	}
};
int tot, first[maxn], x[maxn], y[maxn];
long long dis[maxn];
void add(int a, int b, int c) {
	e[++tot].dis = c; e[tot].to = b; e[tot].next = first[a]; first[a] = tot;
}
int vis[maxn];
priority_queue<node> s;
void dij(int x) {
	dis[1] = 0;
	For(i, 1, n) vis[i] = 0;
	s.push((node) {0, 1});
	while(!s.empty()) {
		node tmp = s.top(); s.pop();
		if (vis[tmp.pos]) continue;
		vis[tmp.pos]++;
		for (int i = first[tmp.pos]; i; i = e[i].next) {
			if (dis[e[i].to] > dis[tmp.pos] + e[i].dis) {
				dis[e[i].to] = dis[tmp.pos] + e[i].dis;
				s.push((node) {dis[e[i].to], e[i].to});
			}
		}
	}
}

bool cmp(zz a, zz b) {
	return a.dis < b.dis;
}
int main(void) {
	cin >> n >> m >> t;
	For(i, 1, n) dis[i] = inf;
	For(i, 1, m) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
	}
	For(i, 1, t) {
		cin >> k[i].to >> k[i].dis;
	}
	dij(1);
	int ans = t;
	sort(k + 1, k + 1 + t, cmp);
	//cout << dis[4] << endl;
	For(i, 1, t) {
		if (dis[k[i].to] > k[i].dis) {
			ans--;
			add(1, k[i].to, k[i].dis);
			dij(1);
		}
	}
	cout << ans << endl;
} 

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 8548K, 提交时间: 2020-03-14 14:07:39

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;i++)
#define maxn 3011010
int tot,dd[maxn],ans,n,m,k;
long long dis[maxn];
struct edge
{
	int x,y,s;
	long long z;
}a[maxn],b[maxn];
bool cmp(edge a,edge b)
{
	return a.z<b.z;
}
void read(long long &x)
{
	x=0;
	long long k=1;
	char s;
	while((s=getchar())!='-'&&s!=EOF&&!isdigit(s));
	if(s=='-')
	{
		k=-1;
		s=getchar();
	};
	while(isdigit(s)) x=x*10+s-'0',s=getchar();
	x=x*k; 
}
void add(int x,int y,long long z)
{
	a[++tot].x=x;
	a[tot].y=y;
	a[tot].z=z;
	a[tot].s=dd[x];
	dd[x]=tot;
}
void spfa(int qd)
{
	queue<int>Q;
	Q.push(qd);
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		for(int i=dd[x];i;i=a[i].s)
		{
			int y=a[i].y;
			if(dis[y]-dis[x]>a[i].z)
			{
				dis[y]=dis[x]+a[i].z;
				Q.push(y);
			}
		}
	}
}
int main()
{
	long long x,y,z;
	scanf("%d %d %d",&n,&m,&k);
	go(i,1,m)
	{
		read(x);
		read(y);
		read(z);
		add(x,y,z);
		add(y,x,z);
	}
	ans=k;
	for(int i=1;i<=n+1;i++) dis[i]=1e15;
	dis[1]=0;
	spfa(1);
	go(i,1,k)
	{
		read(y);
		read(z);
		b[i].y=y;
		b[i].z=z;
	}
	sort(b+1,b+k+1,cmp);
	go(i,1,k)
	{
		y=b[i].y;
		z=b[i].z;
		if(dis[y]>z)
		{
			ans--;
			dis[y]=z;
			add(1,y,z);
			spfa(y);
		}
	}
	printf("%d",ans);
}