Build the shortest path tree

Delete edges in a graph

The problem is described in Chinese. The basic ideas if find k edges after deleting a connected graph to make sure:

the shortest path after deletion can be kept.

The basic idea to solve this problem is keeping the edges which can be used to built the shortest path. Delete the rest then the shortest path to the root node 1 will be preserved.

A naive dijkstra is used here.

#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const LL INF = 1e16;
typedef pair<int, int> PII;
int main(){
    int n, m, k;
    cin >> n >> m >> k;
int x, y, w;
    map<PII, int> id;
    vector<vector<PII>> AL(n+1);
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> w;
        AL[x].emplace_back(y, w);
        AL[y].emplace_back(x, w);
        id[make_pair(x, y)] = i;
        id[make_pair(y, x)] = i;
    }
    if (k==0) {cout << 0<<endl;return 0;}
    // naive dijkstra
    vector<LL> dis(n+1, INF);
    set<PII> pq;
    dis[1] = 0ll;
    for (int i = 1; i <= n; ++i){
        auto v = dis[i];
        pq.emplace(v, i);
    }
    while (!pq.empty()) {
        auto [w, curr_node] = *pq.begin(); pq.erase(pq.begin());
        for (auto [neighbor, w]: AL[curr_node]) 
        {
            auto newdis = (LL)w + dis[curr_node];
            if ( newdis < dis[neighbor]) {
                pq.erase({ dis[neighbor], neighbor});
                pq.emplace(newdis, neighbor);
                dis[neighbor] = newdis;
            }
        }
    }
    vector<int> ret;
    vector<int> stk;
    stk.push_back(1);
    // if not visited, one node might be saved more than one times as there might be more than one shortest path
    // to this node.
    vector<bool>visited(n+1, false); 
    bool done = false;
    // non recursion dfs
    while (!stk.empty() && !done) {
        auto top = stk.back(); stk.pop_back();
        visited[top]= true;
        for ( auto [neighbor, w]: AL[top]) {
            if (!visited[neighbor] && dis[top] + (LL)w == dis[neighbor]) {
                stk.push_back(neighbor);
                ret.push_back(id[make_pair(top, neighbor)]);
                if ((int)ret.size()>= k) {
                    done = true;
                    break;
                }
            }
        }
    }
cout << ret.size() << endl;
    for (auto x: ret) cout << x <<" ";
    cout << endl;
    return 0;
}

Improved version

#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
const LL INF = 1e16;
typedef pair<int, int> PII;
typedef pair<long long, int> PLI;
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    
    int x, y, w;
    map<PII, int> id;
    vector<vector<PII>> AL(n+1);
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> w;
        AL[x].emplace_back(y, w);
        AL[y].emplace_back(x, w);
        id[make_pair(x, y)] = i;
        id[make_pair(y, x)] = i;
    }
    if (k==0) {cout << 0<<endl;return 0;}
    vector<LL> dis(n+1, INF);
    // improved dijkstra
    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;
    pq.emplace(0, 1);
    while (!pq.empty()) {
        auto [d, curr_node] = pq.top(); pq.pop();
        if (d >= dis[curr_node]) continue;
        dis[curr_node] = d;
        for (auto [neighbor, w]: AL[curr_node]) 
        {
            auto newdis = (LL)w + d;
            if ( newdis >= dis[neighbor]) continue;
            pq.emplace(newdis, neighbor);
        }
    }
    vector<int> ret;
    vector<int> stk;
    stk.push_back(1);
    // if not visited, one node might be saved more than one times as there might be more than one shortest path
    // to this node.
    vector<bool>visited(n+1, false); 
    bool done = false;
    while (!stk.empty() && !done) {
        auto top = stk.back(); stk.pop_back();
        visited[top]= true;
        for ( auto [neighbor, w]: AL[top]) {
            if (!visited[neighbor] && dis[top] + (LL)w == dis[neighbor]) {
                stk.push_back(neighbor);
                ret.push_back(id[make_pair(top, neighbor)]);
                if ((int)ret.size()>= k) {
                    done = true;
                    break;
                }
            }
        }
    }
    
    cout << ret.size() << endl;
    for (auto x: ret) cout << x <<" ";
    cout << endl;
    return 0;
}