CF449B Jzzhu and Cities

其实这一道题并不是很难，只是一个最短路而已，请继续看我的题解吧~(^▽^)

AC代码：

#include<bits/stdc++.h>

#define maxn 3000005

#define pa pair<long long,long long>

#define inf 1000000000000000000ll

using namespace std;

long long n,m,k;

struct edge{

	long long val,to;

};

bool vis[maxn];

long long dis[maxn],mark[maxn];

priority_queue<pa,vector<pa>,greater<pa> > q;

vector<edge> e[maxn*3];

long long ans;

void dijkstra()

{

	memset(vis,0,sizeof(vis));

	dis[1]=0;

	q.push(make_pair(0,1));

	while(!q.empty()){

		int x=q.top().second;

		q.pop();

		if(vis[x])

			continue;

		vis[x]=1;

		for(int i=0;i<e[x].size();i++){

			int y=e[x][i].to;

			if(dis[x]+e[x][i].val<=dis[y]){

				if(mark[y]){

					mark[y]=0;

				}

				if(dis[x]+e[x][i].val<dis[y]){

					dis[y]=dis[x]+e[x][i].val;

					q.push(make_pair(dis[y],y));

				}

			}

		}

	}

}

void addedge(long long x,long long y,long long v){

	edge tmp;

	tmp.to=y;

	tmp.val=v;

	e[x].push_back(tmp);

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&k);

	for(int i=1;i<=n;i++)

		dis[i]=inf;

	for(int i=1;i<=m;i++){

		long long x,y,z;

		scanf("%lld%lld%lld",&x,&y,&z);

		addedge(x,y,z);

		addedge(y,x,z);

	}

	for(int i=1;i<=k;i++){

		long long y,z;

		scanf("%lld%lld",&y,&z);

		if(dis[y]>z)

		{

			dis[y]=z;

			q.push(make_pair(z,y));

			mark[y]=1;

		}

	}

	dijkstra();

	for(int i=1;i<=n;i++)

		ans+=mark[i];

	printf("%lld\n",k-ans);

}

详解

那么我们来简化一下题目的含义
就是说有n个城市
1号城市是起点（树的根）
有m条普通边
有k条特殊边
问最多能删掉多少条边，能使最短路径不变

那么我们就可以先把n+k条边跑一遍dijkstra
然后就求出来了每个城市之间的最短路
在跑最短路的过程中判断这k条特殊边是否去掉后不影响最短路

但是这个题还有一个很坑人的bug
就像样例2中的一样，那k条特殊边可能会重复
那其实我们只需要留下来一条最短的就行了
用这个最短的一条去构建最短路
剩下的就直接删掉了
最后只需要用总边数减去剩余的特殊边的数量就行啦!~