fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define N 50001
  5. #define fi first
  6. #define se second
  7. #define MOD 1000000007
  8.  
  9. #define pb push_back
  10.  
  11. #define ll long long
  12.  
  13. #define eps 1.0e-9
  14. #define inf 1e9 + 5
  15. #define double long double
  16.  
  17. #define pp pair<int,int>
  18.  
  19. vector< pp > adj[N];
  20. int dis[N],dp[N];
  21.  
  22. int main()
  23. {
  24.   ios::sync_with_stdio(0);
  25.   int i,j,k,m,n,t;
  26.   cin>>n>>m;
  27.   for(i=0;i<m;i++)
  28.   {
  29.     int u,v,w;
  30.     cin>>u>>v>>w;
  31.     //u--;v--;
  32.     adj[u].pb({w,v});
  33.     adj[v].pb({w,v});
  34.   }
  35.   priority_queue< pp , vector<pp > , greater<pp> > pq;
  36.   for(int i=0;i<=n;i++) dis[i] = INT_MAX;
  37.   dis[1] = 0;
  38.   dp[1] = 1;
  39.   pq.push({0,1});
  40.  
  41.   while(!pq.empty())
  42.   {
  43.     pp tp = pq.top();
  44.     int u = tp.se;
  45.     int d = tp.fi;
  46.     pq.pop();
  47.     if(dis[u]<d) continue;
  48.  
  49.     for(i=0;i<adj[u].size();i++)
  50.     {
  51.       int v = adj[u][i].se;
  52.       int w = adj[u][i].fi;
  53.       if(d + w <= dis[v] )
  54.       {
  55.         //dp[v] += dp[u];
  56. 		if(dis[v]==d+w) dp[v] += dp[u];
  57.         if(d + w < dis[v])
  58.         {
  59.           dis[v] = d + w;
  60.           dp[v] = dp[u];
  61.           pq.push({dis[v],v}); 
  62.         }
  63.       }
  64.     }
  65.   }
  66.  
  67.   cout<<endl;
  68.  
  69.   for(int i = 1;i<=n;i++)
  70.   {
  71.     cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;
  72.   }
  73.  
  74.  
  75.  
  76.  
  77.  
  78. }
Success #stdin #stdout 0s 17624KB
comments (?)
stdin
copy 
3 3
1 2 1
1 3 3
2 3 1
stdout
copy 
1 dis = 0 ways = 1
2 dis = 1 ways = 1
3 dis = 2 ways = 1
https://ideone.com/kYWbPW
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!