fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cmath>
  5. #include <cstdio>
  6. using namespace std;
  7. vector<int> data [10050];
  8. int v,e,a,b,l,s,k,inv,ras,parent;
  9. double ex,ex_help;
  10. vector<double> wt(100001,-1);
  11. int path [100500];
  12. int top_mas [100500];
  13. vector<int> path_help;
  14. vector<int> path_res;
  15. void make()
  16. {
  17.     for (int i=1; i<=wt.size(); i++)
  18.     {
  19.         wt[i]=-1;
  20.     }
  21. }
  22. void Dijkstra(double ex)
  23. {
  24.     make();
  25.     queue<int>t;
  26.     t.push(1);
  27.     wt[1]=0;
  28.     while (!t.empty())
  29.     {
  30.         int top=t.front();
  31.         t.pop();
  32.         for (int i=0; i<data[top].size(); i+=4)
  33.         {
  34.             //cout<<1<<endl;
  35.             //cout<<"!"<<data[top][i+2]/data[top][i+1]<<endl;
  36.             //cout<<data[top][i]<<" "<<wt[data[top][i]]<<endl;
  37.             if (wt[data[top][i]]>(double)data[top][i+2]/((double)data[top][i+1]+(double)ex)+wt[top] || wt[data[top][i]]==-1)
  38.             {
  39.                 //cout<<2<<endl;
  40.                wt[data[top][i]]=(double)data[top][i+2]/((double)data[top][i+1]+(double)ex)+wt[top];
  41.                top_mas[data[top][i]]=top;
  42.                path[data[top][i]]=data[top][i+3];
  43.                 t.push(data[top][i]);
  44.             }
  45.  
  46.         }
  47.     }
  48. }
  49. int main()
  50. {
  51.     cin>>v>>e;
  52.     for (int i=1; i<=e; ++i)
  53.     {
  54.         cin>>a>>b>>s>>l;
  55.         data[a].push_back(b);
  56.         data[a].push_back(s);
  57.         data[a].push_back(l);
  58.         data[a].push_back(i);
  59.         data[b].push_back(a);
  60.         data[b].push_back(s);
  61.         data[b].push_back(l);
  62.         data[b].push_back(i);
  63.     }
  64.     cin>>k;
  65.     ras=1;
  66.     parent=v;
  67.     Dijkstra(0);
  68.     double res_1=wt[v];
  69.     double eps=10e-9;
  70.     double speed_2=10e+12;
  71.     double speed_1=0;
  72.     int Misha=0;
  73.     ex_help=0;
  74.     int iter=0;
  75.     if (wt[v]!=k)
  76.     {
  77.         while(fabs(speed_2-speed_1)>eps)
  78.         {
  79.             ex_help=(speed_1+speed_2)/2;
  80.             Dijkstra(ex_help);
  81.             if (fabs(speed_2-speed_1)<eps)
  82.             break;
  83.             if(wt[v]>k)
  84.             {
  85.                 speed_1=ex_help;
  86.             }
  87.  
  88.             if (wt[v]<k)
  89.             {
  90.                 speed_2=ex_help;
  91.             }
  92.  
  93.  
  94.             ++Misha;
  95.  
  96.         }
  97.     }
  98.  
  99.             while(top_mas[parent]!=1)
  100.             {
  101.                 path_help.push_back(path[parent]);
  102.                 parent=top_mas[parent];
  103.                 ++iter;
  104.             }
  105.         printf("%.6f",ex_help);
  106.         cout<<" "<<iter+1<<endl;
  107.         cout<<path[parent]<<" ";
  108.         for (int i=path_help.size()-1; i>=0; --i)
  109.         {
  110.             cout<<path_help[i]<<" ";
  111.         }
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121. }
Time limit exceeded #stdin #stdout 5s 4210688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oCBl9X
language:
C++ (gcc 8.3)
created:
7 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!