Interview Question Help

Правка en7, от go_rob, 2017-04-03 10:57:15

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] )
      {
        if(dis[v]==d+w) dp[v] += dp[u];

        if(d + w < dis[v])
        {
          dis[v] = d + w;  
          dp[v] = dp[u];
          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;
}
Теги #graph, dijkstra, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский go_rob 2017-04-03 10:57:15 42
en6 Английский go_rob 2017-04-02 20:46:34 2 Tiny change: ' n , m .\nNext m l' -> ' n , m .\n\nNext m l' (published)
en5 Английский go_rob 2017-04-02 20:45:14 71
en4 Английский go_rob 2017-04-02 20:25:38 1356
en3 Английский go_rob 2017-04-02 20:22:29 17
en2 Английский go_rob 2017-04-02 20:21:00 69
en1 Английский go_rob 2017-04-02 20:17:44 764 Initial revision (saved to drafts)