Ce problème concerne un graphe non orienté comportant n sommets et m arêtes pondérées. De plus, il existe k arêtes supplémentaires connectant le sommet 1 à divers autres sommets. L'objectif est de déterminer le nombre maximal d'arêtes parmi ces k arêtes que l'on peut supprimer, tout en garantissant que les distances les plus courtes de tous les sommets au sommet 1 restent inchangées.

Analyse du Problème

Une approche naïve consisterait à tester la suppression de chaque arête parmi les k arêtes individuellement, puis à recalculer les plus courtes distances pour l'ensemble du graphe. Cependant, étant donné que k peut atteindre 105, cette méthode est trop coûteuse en termes de performance.

Une observation clé est que si une arête n'est pas utilisée dans l'une des plus courtes distances depuis le sommet 1, ou si la distance la plus courte au sommet auquel elle est connectée peut être atteinte par plusieurs chemins distincts, alors cette arête peut potentiellement être supprimée.

Pour résoudre ce problème efficacement, nous pouvons adapter un algorithme de plus courte distance, tel que Dijkstra. Pendant l'exécution de Dijkstra, nous devons suivre non seulement la distance la plus courte vers chaque sommet, mais aussi le nombre de chemins distincts qui mènent à cette distance la plus courte. Introduisons une varible path_count[v] pour chaque sommet v, qui compte le nombre de sommets u tels que le chemin le plus court vers v passe par l'arête (u, v) et suit un chemin le plus court depuis le sommet 1 jusqu'à u.

Lors de la mise à jour des distances dans Dijkstra :

• Si la nouvelle distance vers v via u est égale à la distance la plus courte actuelle de v (current_dist[v] == current_dist[u] + edge_weight(u, v)), cela signifie qu'un autre chemin le plus court a été trouvé. Dans ce cas, nous incrémentons path_count[v]. Si des arêtes multiples existent entre u et v avec le même poids, nous devons compter chaque occurrence.
• Si la nouvelle distance vers v via u est strictement plus courte que la distance la plus courte actuelle de v (current_dist[v] > current_dist[u] + edge_weight(u, v)), alors nous avons trouvé un nouveau chemin le plus court. La distance de v est mise à jour, et path_count[v] est réinitialisé à 1 (car ce nouveau chemin est actuellement le seul chemin le plus court connu). Si v n'avait pas été visité auparavant, nous l'ajoutons à la file de priorité.

Une implémentation alternative pour compter les chemins pourrait être :

if (distance[v] == distance[u] + weight(u, v)) {
    path_count[v] += path_count[u];
}
if (distance[v] > distance[u] + weight(u, v)) {
    distance[v] = distance[u] + weight(u, v);
    path_count[v] = path_count[u];
    // Ajouter v à la file de priorité si non visité
}

Cependant, cette approche peut entraîner un nombre exponentiel de chemins dans certains cas, ce qui la rend impraticable. La première approche, qui compte les arêtes incidentes dans les chemins les plus courts, est plus gérable.

Détermination des Arêtes à Supprimer

Après avoir exécuté l'algorithme de plus courte distance et collecté les informatiosn nécessaires, nous pouvons déterminer quelles arêtes parmi les k arêtes peuvent être supprimées. Pour chaque arête supplémentaire connectant le sommet 1 au sommet v avec un poids w :

1. Si la distance la plus courte calculée vers v (shortest_dist[v]) est strictement inférieure à w, cela signifie que l'arête (1, v) avec poids w n'est pas nécessaire pour maintenir la plus courte distance vers v. Elle peut donc être supprimée.
2. Si shortest_dist[v] est égale à w, l'arête (1, v) fait partie d'au moins un chemin le plus court. Dans ce cas, nous devons vérifier path_count[v]. Si path_count[v] > 1, cela indique qu'il existe plusieurs chemins le plus court distincts vers v, et l'arête (1, v) n'est pas unique dans son rôle. Elle peut donc être supprimée. Il est important de décrémenter path_count[v] après avoir compté cette arête comme supprimable, car nous traitons ici des arêtes spécifiques et leur contribution au comptage des chemins.

Le nombre total d'arêtes pouvant être supprimées est la somme des cas ci-dessus.

Implémentation C++

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const long long INF = std::numeric_limits<long long>::max();

struct Edge {
    int to;
    int weight;
    int next;
};

std::vector<Edge> adj[1000012];
int edge_count = 0;
int head[1000012];

void add_edge(int u, int v, int w) {
    edge_count++;
    adj[u].push_back({v, w, head[u]});
    head[u] = edge_count;
}

long long dist[1000012];
int path_counts[1000012];
bool visited[1000012];

struct PriorityInfo {
    long long distance;
    int node;

    bool operator>(const PriorityInfo& other) const {
        return distance > other.distance;
    }
};

void dijkstra(int n) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        path_counts[i] = 0;
        visited[i] = false;
    }
    dist[1] = 0;
    std::priority_queue<PriorityInfo, std::vector<PriorityInfo>, std::greater<PriorityInfo>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        PriorityInfo current = pq.top();
        pq.pop();

        int u = current.node;
        if (visited[u]) continue;
        visited[u] = true;

        for (int i = head[u]; i != 0; i = adj[u][head[u] - i].next) { // Adjusted for 0-based next index if needed
             int v = adj[u][head[u] - i].to;
             int weight = adj[u][head[u] - i].weight;

            if (dist[v] == dist[u] + weight) {
                path_counts[v]++;
            }
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                path_counts[v] = 1;
                if (!visited[v]) {
                    pq.push({dist[v], v});
                }
            }
        }
    }
}

struct ExtraEdge {
    int target_node;
    int weight;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m, k;
    std::cin >> n >> m >> k;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    std::vector<ExtraEdge> extra_edges(k);
    for (int i = 0; i < k; ++i) {
        int s, w;
        std::cin >> s >> w;
        extra_edges[i] = {s, w};
        add_edge(1, s, w);
        add_edge(s, 1, w);
    }

    dijkstra(n);

    int deletable_edges = 0;
    for (int i = 0; i < k; ++i) {
        int v = extra_edges[i].target_node;
        int w = extra_edges[i].weight;

        if (dist[v] < w) {
            deletable_edges++;
        } else if (dist[v] == w) {
            if (path_counts[v] > 1) {
                deletable_edges++;
                path_counts[v]--; // Account for this specific edge
            }
        }
    }

    std::cout << deletable_edges << std::endl;

    return 0;
}