Build the shortest path tree

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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi