fork download
copy 
  1. /// spfa - muoii
  2. /// spfa - vn.spoj.com/problems/NETACCEL/
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define tag "spoj"
  7. #define maxn 1003
  8. #define maxc 207
  9. #define oo 1000000007
  10. #define mid ((l+r)>>1)
  11. #define meset(a,x) memset(a,x,sizeof(a))
  12. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  13. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  14. int n,m,k;
  15. struct neigh{ int ver; double wei; };
  16. struct lala{ int ver,cost; };
  17. vector<neigh> adj[maxn];
  18. double d[maxn][17];
  19. bool inq[maxn][17];
  20. int pw2[17];
  21.  
  22. void spfa(int u)
  23. {
  24.     meset(inq,0);
  25.     meset(d,127);
  26.     pw2[0]=1;for(int i=1;i<17;i++) pw2[i]=pw2[i-1]<<1;
  27.  
  28.     queue<lala> Q;
  29.     d[u][0]=0,Q.push({u,0}),inq[u][0]=1;
  30.  
  31.     int c;
  32.     while (Q.size())
  33.     {
  34.         u=Q.front().ver;
  35.         c=Q.front().cost;
  36.         Q.pop(),inq[u][c]=false;
  37.  
  38.         for (const auto &e: adj[u])
  39.         {
  40.             int v=e.ver; double w=e.wei;
  41.  
  42.             for (int tmp=0;tmp<=k;tmp++)
  43.             {
  44.                 double up=d[v][tmp];
  45.  
  46.                 for (int div=0;div<=tmp;div++) up=min(up,d[u][tmp-div] + w/pw2[div]);
  47.  
  48.                 if (up<d[v][tmp])
  49.                 {
  50.                     d[v][tmp]=up;
  51.                     if (!inq[v][tmp]) Q.push({v,tmp}),inq[v][tmp]=true;
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     #ifdef dmdd
  61.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  62.     #endif // dmdd
  63.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  64.  
  65.     cin>>n>>m>>k;
  66.  
  67.     int x,y; double z;
  68.     while(m-->0) cin>>x>>y>>z,adj[x].push_back({y,z}),adj[y].push_back({x,z});
  69.  
  70.     spfa(1);
  71.  
  72.     cout<<fixed<<setprecision(2);
  73.     cout<<d[n][k]<<"\n";
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 15408KB
comments (?)
stdin
copy 
5 5 2
1 2 1
2 3 9
3 5 1
1 4 5
4 5 5
stdout
copy 
4.25
https://ideone.com/wucb1g
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!