449B

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 $n$ cities ($1 \leq n \leq 10^5) and <span class="arithmatex"><span class="MathJax_Preview">m</span><script type="math/tex">m$ roads ( roads (1 \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;
}