449B


  Posted on 07 Dec 2014
shortest path

Description


The first node of a undirected graph is the capital, whose edges are normal roads. In addition, there are some train routes connecting the capital and other cities. Output how many train routes can be closed without affecting the shortest distance between the capital and each city. There are cities (m1 \leq m \leq 3 \times 10^5).

Tutorial


We initially set the shortest distance to each city by its train route. Then start the Dijkstra algorithm. When updating the distance of a node, if the new distance is less than or equal to the original distance, it means that the train route to that node is not necessary (we find another shortest path other than the train route).

I learned how to define a graph by vector.

vector<pair<int, int> > edge[MAX_NODE_NUM];
edge[u].push_back(make_pair(v, w));

I also updated the template for Dijkstra.

Solution


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX_EDGE_NUM 300005 * 2
#define MAX_NODE_NUM 100005
#define INF (1LL << 60)
#define D(x) 

int node_num, edge_num, route_num;
long long dist[MAX_NODE_NUM];
bool train[MAX_NODE_NUM];
vector<pair<int, int> > edge[MAX_NODE_NUM];

void input()
{
	scanf("%d%d", &node_num, &edge_num);
	scanf("%d", &route_num);
	for (int i = 0; i < edge_num; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		v--;
		u--;
		edge[u].push_back(make_pair(v, w));
		edge[v].push_back(make_pair(u, w));
	}
	fill(dist, dist + node_num, INF);
	fill(train, train + node_num, false);
	for (int i = 0; i < route_num; i++)
	{
		int v, w;
		scanf("%d%d", &v, &w);
		v--;
		dist[v] = min(dist[v], (long long)w);
		train[v] = true;
	}
}

priority_queue<pair<long long, int> > pq;

void dijkstra(int source)
{
	dist[source] = 0;
	pq.push(make_pair(0LL, 0));
	for (int i = 0; i < node_num; i++)
		if (train[i])
		{
			pq.push(make_pair(-dist[i], i));
		}
	while (!pq.empty())
	{
		int u = pq.top().second;
		long long w = -pq.top().first;
		pq.pop();
		if (dist[u] != w)
			continue;
		for (int i = 0; i < (int)edge[u].size(); i++)
		{
			int v = edge[u][i].first;
			long long new_w = edge[u][i].second + w;
			if (dist[v] >= new_w && train[v])
			{
				train[v] = false;
			}
			if (dist[v] > new_w)
			{
				dist[v] = new_w;
				pq.push(make_pair(-dist[v], v));
			}
		}
	}
}

int work()
{
	int ret = route_num;
	for (int i = 0; i < node_num; i++)
	{
		if (train[i])
		{
			ret--;
		}
	}
	return ret;
}

int main()
{
	input();
	dijkstra(0);
	printf("%d\n", work());
	return 0;
}