There are n nodes(1,2.. n) in a `weighted graph` with `m (m>n) bi-directional edges`. ↵
↵
`All weights are positive and there are no multiple edges`.↵
↵
There is one `fixed origin(Node 1)`. We will always start traveling from the origin. ↵
↵
Now we have to find the `number of ways to reach each of the nodes(starting from the origin) with minimum cost`.(All paths counted should have the minimum cost to reach that node).↵
↵
Expected complexity O(m*log(m)).↵
↵
↵
Input — First line contains n , m .↵
↵
Next m lines contain u,v,w. => There is an edge between u and v of weight w(w>0).↵
↵
Output — Print n-1 lines one for each node other than origin, containing the number of ways to reach each of the nodes(starting from the origin) with minimum cost.↵
↵
Sample Test -↵
↵
4 5↵
↵
1 2 5↵
↵
1 3 3↵
↵
3 2 2↵
↵
3 4 7↵
↵
2 4 5↵
↵
Output — ↵
↵
2↵
↵
1 ↵
↵
3↵
↵
Here is my solution, Please check if this will work for all cases, I did modified Dijkstra + DP.↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define N 5001↵
#define fi first↵
#define se second↵
#define MOD 1000000007↵
↵
#define pb push_back↵
↵
#define ll long long↵
↵
#define eps 1.0e-9↵
#define inf 1e9 + 5↵
#define double long double↵
↵
#define pp pair<int,int>↵
↵
vector< pp > adj[N];↵
int dis[N],dp[N];↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
int i,j,k,m,n,t;↵
cin>>n>>m;↵
for(i=0;i<m;i++)↵
{↵
int u,v,w;↵
cin>>u>>v>>w;↵
//u--;v--;↵
adj[u].pb({w,v});↵
adj[v].pb({w,v});↵
}↵
priority_queue< pp , vector<pp > , greater<pp> > pq;↵
for(int i=0;i<=n;i++) dis[i] = INT_MAX;↵
dis[1] = 0;↵
dp[1] = 1;↵
pq.push({0,1});↵
↵
while(!pq.empty())↵
{↵
pp tp = pq.top();↵
int u = tp.se;↵
int d = tp.fi;↵
pq.pop();↵
if(dis[u]<d) continue;↵
↵
for(i=0;i<adj[u].size();i++)↵
{↵
int v = adj[u][i].se;↵
int w = adj[u][i].fi;↵
if(d + w <= dis[v] )↵
{↵
dp[v] += dp[u];↵
↵
if(d + w < dis[v])↵
{↵
dis[v] = d + w; ↵
pq.push({dis[v],v}); ↵
}↵
}↵
}↵
}↵
↵
cout<<endl;↵
↵
for(int i = 1;i<=n;i++)↵
{↵
cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
↵
↵
`All weights are positive and there are no multiple edges`.↵
↵
There is one `fixed origin(Node 1)`. We will always start traveling from the origin. ↵
↵
Now we have to find the `number of ways to reach each of the nodes(starting from the origin) with minimum cost`.(All paths counted should have the minimum cost to reach that node).↵
↵
Expected complexity O(m*log(m)).↵
↵
↵
Input — First line contains n , m .↵
↵
Next m lines contain u,v,w. => There is an edge between u and v of weight w(w>0).↵
↵
Output — Print n-1 lines one for each node other than origin, containing the number of ways to reach each of the nodes(starting from the origin) with minimum cost.↵
↵
Sample Test -↵
↵
4 5↵
↵
1 2 5↵
↵
1 3 3↵
↵
3 2 2↵
↵
3 4 7↵
↵
2 4 5↵
↵
Output — ↵
↵
2↵
↵
1 ↵
↵
3↵
↵
Here is my solution, Please check if this will work for all cases, I did modified Dijkstra + DP.↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define N 5001↵
#define fi first↵
#define se second↵
#define MOD 1000000007↵
↵
#define pb push_back↵
↵
#define ll long long↵
↵
#define eps 1.0e-9↵
#define inf 1e9 + 5↵
#define double long double↵
↵
#define pp pair<int,int>↵
↵
vector< pp > adj[N];↵
int dis[N],dp[N];↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
int i,j,k,m,n,t;↵
cin>>n>>m;↵
for(i=0;i<m;i++)↵
{↵
int u,v,w;↵
cin>>u>>v>>w;↵
//u--;v--;↵
adj[u].pb({w,v});↵
adj[v].pb({w,v});↵
}↵
priority_queue< pp , vector<pp > , greater<pp> > pq;↵
for(int i=0;i<=n;i++) dis[i] = INT_MAX;↵
dis[1] = 0;↵
dp[1] = 1;↵
pq.push({0,1});↵
↵
while(!pq.empty())↵
{↵
pp tp = pq.top();↵
int u = tp.se;↵
int d = tp.fi;↵
pq.pop();↵
if(dis[u]<d) continue;↵
↵
for(i=0;i<adj[u].size();i++)↵
{↵
int v = adj[u][i].se;↵
int w = adj[u][i].fi;↵
if(d + w <= dis[v] )↵
{↵
dp[v] += dp[u];↵
↵
if(d + w < dis[v])↵
{↵
dis[v] = d + w; ↵
pq.push({dis[v],v}); ↵
}↵
}↵
}↵
}↵
↵
cout<<endl;↵
↵
for(int i = 1;i<=n;i++)↵
{↵
cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
↵
