fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define sll(n) scanf("%lld",&(n))
  3. #define sll2(m,n) scanf("%lld%lld",&(m),&(n))
  4. #define sll3(m,n,o) scanf("%lld%lld%lld",&(m),&(n),&(o))
  5. #define sll4(m,n,o,p) scanf("%lld%lld%lld%lld",&(m),&(n),&(o),&(p))
  6. #define pll(n) printf("%lld ",(n))
  7. #define plln(n) printf("%lld\n",(n))
  8. #define ps(s) printf("%s",(c_str(s)))
  9. #define psn(s) printf("%s\n",(c_str(s)))
  10. #define nln printf("\n")
  11. #define cln cout<<"\n"
  12. #define clr(dp,x) memset(dp,x,sizeof(dp))
  13. #define pb push_back
  14. #define mp make_pair
  15. #define s(a) sort(a.begin(),a.end())
  16. #define sa(a,n) sort(a,a+(n))
  17. #define vecll vector<long long int>
  18. #define vecs vector<string>
  19. #define vecpll vector<pair<long long int,long long int> >
  20. #define pii pair <long long int , long long int >
  21. #define plpl pair <long long int , pair <long long int , long long int > >
  22. #define ppll pair < pair <long long int , long long int > , long long int >
  23. #define pplpl pair < pair <long long int , long long int >, pair <long long int , long long int > >
  24. //#define rep(i, begin, end) for (__typeof(end) i = (begin); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  25. #define rep(i,a,n) for(__typeof(n) i=a;i<n;++i)
  26. #define repr(i,b,a) for(__typeof(b) i=b;i>=a;--i)
  27. #define rep1(it,v) for(auto &it:(v))
  28. #define all(c) (c).begin(),(c).end()
  29. #define fast_IO ios_base::sync_with_stdio(false);cin.tie(0);
  30. #define while_tc int64_t t;sll(t);while(t--)
  31. #define adjlw vector<vecpll >  /// ( connected to , weight ) - adjlw adj(MAXN)
  32. #define adjl vecll ///connected to - adjl adj[MAXN]
  33. #define ispow2(n) (n&&(!(n&(n-1))))      ///check if its perfect power of 2
  34. #define ff first
  35. #define ss second
  36. #define gcd(a,b) __gcd(a,b)
  37. #define bit(mask) __builtin_popcount(mask)
  38. #define lsb(x) __builtin_ffl(x)-1
  39. typedef int64_t ll;
  40. ll INF=1000000000;
  41. ll MOD=1000000007;
  42. ll MOD2 = MOD*MOD;
  43. double pi=2*acos(0.0);
  44. typedef unsigned long long int ull; /// specifier - llu
  45. using namespace std;
  46.  
  47. inline ll expo(ll e, ll n){ll x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
  48. inline ll power(ll e, ll n, ll m){ll x=1,p=e;while(n){if(n&1)x=(x*p)%m;p=(p*p)%m;n>>=1;}return x;}
  49. inline ll InverseEuler(ll a, ll m){return (a==1? 1 : power(a, m-2, m));}
  50. inline ll lcm(ll a, ll b){return (a*(b/gcd(a,b)));}
  51. inline ll InverseEuclid(ll a, ll m){ll m0=m,t,q,x0=0,x1=1;if(m==1)return 0;while (a>1){q=a/m;t=m;m=a%m;a=t;t=x0;x0=x1-q*x0;x1=t;}return(x1<0?x1+m0:x1);}
  52. //inline ll CRT(){ll M=1,ans=0;rep(i,0,n)M*=num[i];rep(i,0,n)ans=(ans%M+(rem[i]%M*(M/num[i])*(InverseEuclid(M/num[i],num[i]))%M)%M)%M;return ans;}
  53.  
  54.  
  55. ll movex8[]={-1,-1,-1,0,0,1,1,1};
  56. ll movey8[]={-1,0,1,-1,1,-1,0,1};
  57.  
  58. ll movex4[]={1,-1,0,0};
  59. ll movey4[]={0,0,1,-1};
  60.  
  61.  
  62. vector <pair <ll, pair <double, double> > >v[101]; /// to, wt
  63. vecll path(101, -1), restore;
  64. ll s, t, n, m, x, y;
  65. double r, d = 0, ans = 0;
  66. vector <double> dist(101, INF+0.0);
  67.  
  68.  
  69. inline bool dijkstra(double temp, bool ha)
  70. {
  71.     priority_queue <pair <double, ll> > q;
  72.     while (!q.empty())
  73.         q.pop();
  74.     rep(i, 0, n+1)
  75.     {
  76.         dist[i] = INF + 0.0;
  77.         path[i] = -1;
  78.     }
  79.     dist[s] = 0;
  80.     q.push(mp(0,s));
  81.     while (!q.empty())
  82.     {
  83.         ll from = q.top().ss;
  84.         double len = -q.top().ff;   /// path length upto q.front.ss;
  85.         q.pop();
  86.  
  87.         if (len > dist[from])     /// dist[from] may have been modified to lesser value than previously queued len
  88.             continue;
  89.  
  90.         for (auto &it : v[from])
  91.         {
  92.  
  93.             ll to = it.ff;
  94.             double t1 = it.ss.ff;
  95.             double wt = it.ss.ss;
  96.  
  97.             if ((dist[from] +  wt < dist[to]) && (t1 <= temp))
  98.             {
  99.                 dist[to] = dist[from] + wt;
  100.                 path[to] = from;
  101.                 q.push(mp( -dist[to], to));
  102.             }
  103.         }
  104.     }
  105.     if (ha)
  106.     {
  107.         restore.clear();
  108.         for (ll x1 = t; x1!=s ; x1 = path[x1])
  109.             restore.pb(x1);
  110.         restore.pb(s);
  111.     }
  112.     if (dist[t] >= INF || dist[t]<0)
  113.         return false;
  114.     else
  115.         return true;
  116. }
  117.  
  118.  
  119.  
  120. int main()
  121. {
  122.     //freopen("input.txt","r",stdin);
  123. 	//freopen("output.txt","w",stdout);
  124. 	//fast_IO
  125. 	while(sll2(n, m)!=EOF)
  126. 	{
  127. 	    double l=0, h=0;
  128. 	    sll2(s, t);
  129. 	    rep(i, 0, n+1)
  130.             v[i].clear();
  131. 	    rep(i, 0, m)
  132. 	    {
  133. 	        scanf("%lld%lld%lf%lf", &x, &y, &r, &d);
  134. 	        v[x].pb(mp(y, mp(r, d)));
  135. 	        v[y].pb(mp(x, mp(r, d)));
  136. 	        h=max(h, r);
  137. 	    }
  138. 	    h+=1.0;
  139. 	    while(l<=h)
  140.         {
  141.             double mid = ((l+h)/2.0);
  142.             if (dijkstra(mid, false))
  143.             {
  144.                 ans = mid;
  145.                 h = mid - 0.01;
  146.             }
  147.             else
  148.                 l = mid + 0.01;
  149.         }
  150.         ll p = ans*10;
  151.         ans = p/10 + (0.1)*(p%10);
  152.         dijkstra(ans, true);
  153.         reverse(all(restore));
  154.         rep(i, 0, restore.size()-1)
  155.             pll(restore[i]);
  156.         printf("%lld\n", restore[restore.size()-1]);
  157.         printf("%0.1lf %0.1lf\n", dist[t], ans);
  158. 	}
  159. 	return 0;
  160. }
  161.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FeHANl
language:
C++14 (gcc 8.3)
created:
8 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!