CSES - KILO 2015 5/5

Submission details
Task:	Flights
Sender:	🐟FishyGoldenBeetroot
Submission time:	2015-10-07 18:50:01 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.22 s	details
#2	ACCEPTED	0.08 s	details
#3	ACCEPTED	0.21 s	details
#4	ACCEPTED	0.20 s	details
#5	ACCEPTED	0.21 s	details
#6	ACCEPTED	0.15 s	details
#7	ACCEPTED	0.21 s	details
#8	ACCEPTED	0.10 s	details
#9	ACCEPTED	0.20 s	details
#10	ACCEPTED	0.14 s	details
#11	ACCEPTED	0.21 s	details
#12	ACCEPTED	0.11 s	details
#13	ACCEPTED	0.25 s	details
#14	ACCEPTED	0.18 s	details
#15	ACCEPTED	0.24 s	details
#16	ACCEPTED	0.08 s	details
#17	ACCEPTED	0.22 s	details
#18	ACCEPTED	0.14 s	details
#19	ACCEPTED	0.22 s	details
#20	ACCEPTED	0.18 s	details
#21	ACCEPTED	0.22 s	details
#22	ACCEPTED	0.08 s	details
#23	ACCEPTED	0.21 s	details
#24	ACCEPTED	0.14 s	details
#25	ACCEPTED	0.21 s	details
#26	ACCEPTED	0.10 s	details
#27	ACCEPTED	0.22 s	details
#28	ACCEPTED	0.17 s	details
#29	ACCEPTED	0.23 s	details
#30	ACCEPTED	0.17 s	details

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ii, ii> pp;
#define A first
#define B second
#define I A
#define C B.A
#define X B.B
const ll INF = (ll)1e17;

ll bestFwd[(int)2e5] = {0};
ll bestBck[(int)2e5] = {0};

void dist(int start, vector<ii>* adj, ll* best) {
  fill_n(best, (int)2e5, INF);
  priority_queue<ii, vector<ii>, greater<ii>> q;
  q.push(ii(0, start));
  best[start] = 0;
  while(!q.empty()) {
    ii t = q.top();
    q.pop();
    ll c = t.first;
    ll i = t.second;
    if(c > best[i]) continue;
    for(ii edge : adj[i]) {
      int adjI = edge.A;
      ll p = edge.B;
      if(c + p < best[adjI]) {
	best[adjI] = c + p;
	q.push(ii(best[adjI], adjI));
      }
    }
  }
}

int main() {
  vector<ii> f[(int)1.1e5];
  vector<ii> r[(int)1.1e5];
  vector<pp> e;
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    f[a].push_back(ii(b, c));
    r[b].push_back(ii(a, c));
    e.push_back(pp(ii(a, b), ii(c, x)));
  }
  dist(1, f, bestFwd);
  dist(n, r, bestBck);
  double best = (double)INF;
  for(pp p : e) {
    ii ab = p.A;
    ii cx = p.B;
    ll cost = bestFwd[ab.A] + bestBck[ab.B] + cx.A;
    double mul = cx.B * 0.01;
    best = min(best, cost * mul);
  }
  cout << setprecision(17) << best << "\n";
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`100000 200000 83440 84424 708810295 87 28725 29724 552336091 3 76873 79637 768853492 82 73157 75801 208773467 95 ...` view save

correct output
`176693844.03` view save

user output
`176693844.03` view save

Test 2

Verdict: ACCEPTED

input
`4158 76239 2106 2107 214369404 9 2615 2616 599912001 65 2736 2737 106730531 5 3122 3123 989740491 72 ...` view save

correct output
`2980020476.98` view save

user output
`2980020476.98` view save

Test 3

Verdict: ACCEPTED

input
`100000 200000 61333 61375 934791657 27 57230 57459 363488259 89 94862 95081 574564520 83 29350 29358 205892730 47 ...` view save

correct output
`2063342137.46` view save

user output
`2063342137.46` view save

Test 4

Verdict: ACCEPTED

input
`55959 184823 48935 48939 66931740 65 55879 55910 682673953 74 23663 23698 990216382 44 42486 42505 972883623 27 ...` view save

correct output
`4779099645.25` view save

user output
`4779099645.25` view save

Test 5

Verdict: ACCEPTED

input
`100000 200000 79146 79332 484554310 35 52757 52824 784839804 4 63169 63197 671959358 77 38542 38830 850962666 26 ...` view save

correct output
`1273046189.67` view save

user output
`1273046189.6700001` view save

Test 6

Verdict: ACCEPTED

input
`15536 166330 14900 14902 921455515 89 9329 9332 365143744 14 13868 13871 328203159 78 7822 7824 990983220 54 ...` view save

correct output
`6582993331.15` view save

user output
`6582993331.1500006` view save

Test 7

Verdict: ACCEPTED

input
`100000 200000 89124 91195 199647214 2 58704 58990 98401141 40 56447 57157 120977342 98 65418 67693 530932650 5 ...` view save

correct output
`234347497.33` view save

user output
`234347497.33000001` view save

Test 8

Verdict: ACCEPTED

input
`36932 93986 13379 23634 481615407 80 11370 22629 626275451 41 6043 11090 696835009 43 24878 31930 227873837 15 ...` view save

correct output
`41484417.04` view save

user output
`41484417.039999999` view save

Test 9

Verdict: ACCEPTED

input
`100000 200000 81515 81926 207016347 20 93172 93603 517064812 89 27081 27270 942564502 93 65710 66430 161755057 23 ...` view save

correct output
`663852899.14` view save

user output
`663852899.13999999` view save

Test 10

Verdict: ACCEPTED

input
`4286 186778 1008 1009 298863636 25 3735 3736 691053215 32 2583 2584 141648549 63 1362 1363 132628814 52 ...` view save

correct output
`1265736627.37` view save

user output
`1265736627.3700001` view save

Test 11

Verdict: ACCEPTED

input
`100000 200000 39274 41223 667509717 39 17668 18392 794560732 87 84624 85119 258645192 82 39687 40083 222180448 9 ...` view save

correct output
`204801135.31` view save

user output
`204801135.31` view save

Test 12

Verdict: ACCEPTED

input
`156 196340 115 120 885358263 74 69 70 733840613 66 47 51 194519228 36 143 144 997357319 98 ...` view save

correct output
`234518.53` view save

user output
`234518.53` view save

Test 13

Verdict: ACCEPTED

input
`100000 200000 61800 98622 689416865 94 93496 96677 968883683 26 30065 73258 40047565 96 11930 20180 777906649 69 ...` view save

correct output
`46500624.37` view save

user output
`46500624.369999997` view save

Test 14

Verdict: ACCEPTED

input
`58203 168742 20492 20819 512664683 45 35979 36073 406549228 72 22670 22884 958846926 50 3181 3366 812137674 64 ...` view save

correct output
`192471624.40` view save

user output
`192471624.40000001` view save

Test 15

Verdict: ACCEPTED

input
`100000 200000 53792 75073 320931265 77 27716 53886 29596596 82 9946 19018 891154582 91 414 66597 2097895 61 ...` view save

correct output
`52804878.55` view save

user output
`52804878.550000004` view save

Test 16

Verdict: ACCEPTED

input
`29790 51057 6914 7959 559807642 87 4772 6061 707689095 28 12502 14138 473393199 55 16425 16862 224827374 16 ...` view save

correct output
`96426328.10` view save

user output
`96426328.100000009` view save

Test 17

Verdict: ACCEPTED

input
`100000 200000 49413 51160 127588771 32 34728 34779 643912757 70 14609 15317 638237969 84 72278 72351 726808755 98 ...` view save

correct output
`231729444.89` view save

user output
`231729444.89000002` view save

Test 18

Verdict: ACCEPTED

input
`16757 154256 1874 1903 580982686 96 14236 14609 288982257 24 11085 11417 670713941 5 15130 15467 715203324 50 ...` view save

correct output
`47919755.92` view save

user output
`47919755.920000002` view save

Test 19

Verdict: ACCEPTED

input
`100000 200000 81960 97123 353071177 60 77895 83362 530318855 51 88788 96462 763556172 10 71069 89886 859574737 51 ...` view save

correct output
`46970338.23` view save

user output
`46970338.230000004` view save

Test 20

Verdict: ACCEPTED

input
`36582 167647 16230 16359 131627754 74 29007 29070 968621666 86 29854 30031 159358481 31 12010 12340 159218511 83 ...` view save

correct output
`245097346.41` view save

user output
`245097346.41` view save

Test 21

Verdict: ACCEPTED

input
`100000 200000 24087 24412 947358065 23 43122 45521 695825811 46 41701 43009 282526216 22 54644 55241 663868618 22 ...` view save

correct output
`182454553.20` view save

user output
`182454553.20000002` view save

Test 22

Verdict: ACCEPTED

input
`19505 82130 10844 11159 72114176 12 2598 2890 247996564 65 16334 16419 152514701 1 6449 6630 826660090 3 ...` view save

correct output
`90750315.08` view save

user output
`90750315.079999998` view save

Test 23

Verdict: ACCEPTED

input
`100000 200000 18237 23377 495435695 99 64625 68562 165710300 17 92456 92551 809687286 63 69882 70839 463068629 94 ...` view save

correct output
`107349070.08` view save

user output
`107349070.08` view save

Test 24

Verdict: ACCEPTED

input
`24334 122357 20514 20821 536592664 40 3254 4063 271689487 32 16094 17795 378738726 16 19192 21939 488115831 75 ...` view save

correct output
`21531136.12` view save

user output
`21531136.120000001` view save

Test 25

Verdict: ACCEPTED

input
`100000 200000 52201 52304 516199490 3 44594 44790 845780568 84 99131 99307 50245171 79 32481 32509 152614952 8 ...` view save

correct output
`2641004228.19` view save

user output
`2641004228.1900001` view save

Test 26

Verdict: ACCEPTED

input
`26099 89426 8222 8817 421562264 91 21504 21939 928132818 10 13949 14159 774448630 76 19315 19751 984491893 32 ...` view save

correct output
`133812727.09` view save

user output
`133812727.09` view save

Test 27

Verdict: ACCEPTED

input
`100000 200000 58145 58370 637242643 19 24491 24661 262541209 9 62570 62672 413680288 49 71890 72126 53363827 82 ...` view save

correct output
`1253750128.48` view save

user output
`1253750128.48` view save

Test 28

Verdict: ACCEPTED

input
`35877 163659 5428 5668 961665808 94 11515 11541 884764784 34 7511 7652 62813799 11 10211 10835 442538859 55 ...` view save

correct output
`114218011.47` view save

user output
`114218011.47` view save

Test 29

Verdict: ACCEPTED

input
`100000 200000 32689 38720 604086442 75 17653 27003 200982141 20 5642 19524 176519335 85 44331 52918 623420216 30 ...` view save

correct output
`42422753.58` view save

user output
`42422753.579999998` view save

Test 30

Verdict: ACCEPTED

input
`71343 146160 24454 24767 601993050 84 22024 22056 179622315 81 51552 52291 321098922 17 50645 50972 583641105 77 ...` view save

correct output
`407548924.88` view save

user output
`407548924.88` view save

KILO 2015 5/5

Flights

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Tasks

Submissions (🐟FishyGoldenBeetroot)