Problem Link: https://onlinejudge.org/external/128/12878.pdf
Note: After reading this problem, the first intuition that should come is we’ll need the exact path each shortest distance is taking. We cannot count any edge leading to the shortest path more than once.
I followed that intuition and so took a 2D vector named parent which will mainly contain the parent of each node leading to the destination node. I have kept the length info too in the parent vector to use that later while summing up the total value of lengths.
So this problem is using basic Dijkstra, only with a tweak in the approach. Here the tweak I used is in updating the parent vector properly which is containing all the routes that lead to the shortest distance. And later only traversing the parent vector to collect the sum of all shortest paths.
Code:
#include <bits/stdc++.h>
#define MAX 100005
#define INF INT_MAX
#define pii pair<int,int>
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
using namespace std;
void dijkstra(int src, int dst, vector<vector<pii>> &adj, vector<vector<pii>> &parent)
{
vector<int> dis(MAX, INF);
dis[src]=0;
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.
while(!pq.empty())
{
int u=pq.top().second;
int cost=pq.top().first;
pq.pop();
//Optimization in the priority queue:
/*
Ideally, for updating the priority queue, we must delete the old value and reinsert with the
new cost value. But, as we know that the updated cost value is always lesser than the old
value and would be popped from the queue and visited before the old value,
we could save time and avoid removing the old value from the queue.
*/
if(dis[u]<cost) continue;
for(int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
cost=adj[u][i].second;
if(dis[v]>dis[u]+cost)
{
dis[v]=dis[u]+cost;
pq.push({dis[v], v});
parent[v].clear();
parent[v].push_back({cost, u});
}
else if(dis[v]==dis[u]+cost)
{
parent[v].push_back({cost, u});
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int node, edge;
while(cin>>node>>edge)
{
vector<vector<pii> > adj(node);
//vector<pair<int,int>> adj[node]; //can also be written like this
for(int i=0; i<edge; i++)
{
int from,to,cost;
cin>>from>>to>>cost;
adj[from].push_back({to, cost});
adj[to].push_back({from, cost});
}
int src=0, dst=node-1;
vector<vector<pii> > parent(node);
dijkstra(src, dst, adj, parent);
queue<int> q;
q.push(node-1);
int ans=0;
vector<int> vis(node,0);
while(!q.empty())
{
int u=q.front();
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0; i<parent[u].size(); i++)
{
ans+=parent[u][i].first;
q.push(parent[u][i].second);
}
}
cout<<ans*2<<endl;
}
return 0;
}
Fall out, Codes! 