Code Submission Evaluation System Login

Datatähti 2016 alku

Start:2015-09-28 00:00:00
End:2015-10-12 00:00:00
 

Tasks | Scoreboard | Statistics


CSES - Datatähti 2016 alku - Results
History
2015-10-11 12:59:0024
2015-10-11 12:49:420
2015-10-10 20:33:2661
2015-10-01 00:59:3224
2015-10-01 00:58:110
Task:Lennot
Sender:AnttiR
Submission time:2015-10-10 20:33:26
Language:Python3
Status:READY
Score:61

Feedback

groupverdictscore
#1ACCEPTED24
#2ACCEPTED37
#3TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.09 / 1.001details
#2ACCEPTED0.09 / 1.001details
#3ACCEPTED0.08 / 1.001details
#4ACCEPTED0.08 / 1.001details
#5ACCEPTED0.08 / 1.001details
#6ACCEPTED0.25 / 1.002details
#7ACCEPTED0.48 / 1.002details
#8ACCEPTED0.15 / 1.002details
#9ACCEPTED0.35 / 1.002details
#10ACCEPTED0.19 / 1.002details
#11TIME LIMIT EXCEEDED-- / 1.003details
#12TIME LIMIT EXCEEDED-- / 1.003details
#13TIME LIMIT EXCEEDED-- / 1.003details
#14TIME LIMIT EXCEEDED-- / 1.003details
#15TIME LIMIT EXCEEDED-- / 1.003details
#16TIME LIMIT EXCEEDED-- / 1.003details
#17TIME LIMIT EXCEEDED-- / 1.003details

Code

highestPrice = 10**12
class Node:
	def __init__(self):
		self.connections = [] # Tuples of node 's and ints (prices)
		self.cheapest = [highestPrice,highestPrice] #even, odd
		# If moving from a node's odd cost, the flight is free!

nodes, connections = [int(x) for x in input().split(" ")]
notFoundNodes = []
for ni in range(0,nodes):
	newNode = Node()
	notFoundNodes.append(newNode)

for ci in range(0,connections):
	o,t,p = [int(x) for x in input().split(" ")]
	notFoundNodes[o-1].connections.append((notFoundNodes[t-1],p))
  
notFoundNodes[0].cheapest[0] = 0

cheapestTotalPrice = 0

# Djikstra with a few modifications
while True:
	smallestPrice = highestPrice
	smallestPriceNode = []
	
	# Find cheapest node
	for nd in notFoundNodes:
		evenPrice = nd.cheapest[0]
		oddPrice = nd.cheapest[1]
		if evenPrice == -1:
			if oddPrice != -1:
				if oddPrice < smallestPrice:
					smallestPriceNode = [nd,1]
					smallestPrice = oddPrice
		elif oddPrice == -1:
			if evenPrice != -1:
				if evenPrice < smallestPrice:
					smallestPriceNode = [nd,0]
					smallestPrice = evenPrice
		else:
			if oddPrice < evenPrice:
				if oddPrice < smallestPrice:
					smallestPriceNode = [nd,1]
					smallestPrice = oddPrice
			else:
				if evenPrice < smallestPrice:
					smallestPriceNode = [nd,0]
					smallestPrice = evenPrice
					
	# Update connections of cheapest node
	cn = smallestPriceNode[0]
	if cn is notFoundNodes[-1]:
		cheapestTotalPrice = smallestPrice
		break
	oe = (smallestPriceNode[1] + 1) % 2
	for co in cn.connections:
		cost = smallestPrice + co[1] * oe
		target = co[0]
		if target.cheapest[oe] > cost:
			target.cheapest[oe] = cost
			
	# Nullify the current node
	cn.cheapest[smallestPriceNode[1]] = -1
	if cn.cheapest[0] == -1 and cn.cheapest[1] == -1:
		notFoundNodes.remove(cn)

print (cheapestTotalPrice)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 20
2 1 3
7 6 4
1 6 7
1 6 1
3 10 3
9 3 6
6 2 10
2 6 3
1 8 6
2 8 6
4 5 1
7 6 3
8 4 5
9 5 5
9 10 7
3 9 6
5 3 8
2 1 3
1 4 5
...
view   save

correct output
8
view   save

user output
8
view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
10 20
4 3 10
1 10 9
3 4 10
2 6 7
2 7 2
3 1 2
4 6 7
9 5 4
9 5 2
3 4 10
6 2 9
5 8 8
8 1 5
10 3 4
5 8 2
10 1 1
1 3 1
2 4 5
2 7 8
...
view   save

correct output
9
view   save

user output
9
view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
10 20
5 7 4
6 1 1
7 3 8
8 4 2
6 2 3
10 6 9
6 1 6
9 2 10
3 9 3
2 10 2
9 10 8
7 3 6
5 7 6
8 4 8
10 9 4
9 10 1
4 5 1
6 1 4
1 6 6
...
view   save

correct output
8
view   save

user output
8
view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
10 20
1 6 2
5 3 3
7 3 6
5 6 2
3 4 10
2 10 2
1 6 7
4 7 8
9 8 9
1 5 3
3 4 7
10 8 5
6 3 3
10 9 5
5 6 9
2 7 3
6 5 9
8 9 10
3 5 2
...
view   save

correct output
13
view   save

user output
13
view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
10 20
10 8 5
2 4 7
9 4 7
9 4 1
6 5 7
1 8 9
1 10 9
2 3 1
8 7 6
7 6 3
6 5 10
5 3 1
3 2 5
10 7 5
1 10 8
6 3 4
5 7 4
9 2 1
1 10 4
...
view   save

correct output
4
view   save

user output
4
view   save

Test 6

Group: 2

Verdict: ACCEPTED

input
1000 2000
91 828 365044406
17 984 445675537
251 852 100987451
907 487 58830088
330 385 418647668
536 322 13902478
14 131 176035513
842 640 349320953
801 11 848844995
633 564 510323743
554 577 602789230
423 888 835326635
564 434 428275586
439 393 483763398
483 274 815922872
691 104 507941832
325 590 618432016
615 791 207467588
265 16 880171713
...
view   save

correct output
11893353673
view   save

user output
11893353673
view   save

Test 7

Group: 2

Verdict: ACCEPTED

input
1000 2000
722 939 530579090
404 606 268877348
133 750 760086153
506 46 582310443
919 805 48119731
216 497 987564921
688 703 58956144
248 526 339959001
996 65 338882921
523 123 604765102
834 894 90118472
951 788 973124369
693 148 569643819
940 167 157258543
323 694 146949125
242 238 731193775
995 733 550919757
646 16 791418452
966 409 760742424
...
view   save

correct output
30248963445
view   save

user output
30248963445
view   save

Test 8

Group: 2

Verdict: ACCEPTED

input
1000 2000
340 237 43690066
217 141 453160975
744 202 639037814
605 926 404985542
364 767 11240650
116 495 800978683
666 916 795700314
67 954 158962570
314 927 821562538
959 196 325114995
884 462 755167248
175 802 438729355
857 102 891684566
68 865 593380792
682 608 380623094
287 35 875208643
355 242 609011072
112 657 903744064
359 542 286164651
...
view   save

correct output
3126797692
view   save

user output
3126797692
view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
1000 2000
88 312 190442306
480 402 411574469
29 901 397491243
636 459 323246996
452 37 828529684
39 516 418061741
382 685 301044599
899 364 534095263
362 588 62043917
354 375 579036281
990 536 190613416
756 842 626391500
246 854 757939739
588 263 632978222
52 196 678338775
599 877 631864853
107 497 550050606
300 775 755183437
302 456 852723687
...
view   save

correct output
18416073173
view   save

user output
18416073173
view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
1000 2000
333 228 718389176
796 286 323493090
743 43 751876815
128 554 175625940
931 997 418408353
941 760 543284679
993 804 616120905
697 489 213909773
910 56 472309842
950 476 64495844
142 419 757592473
635 199 204072319
777 616 142052269
872 380 690960817
765 604 246429343
128 654 276155495
577 527 373439677
76 16 633138779
765 591 795963426
...
view   save

correct output
6399349335
view   save

user output
6399349335
view   save

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
28264 92686 186865663
92570 33956 925976418
87377 71249 644757113
16701 81203 922125505
47625 29103 656130402
37860 76695 834361504
25644 44600 352281507
58480 50673 966959214
35810 70949 375259274
11364 84992 404731480
86623 17713 53573081
22060 3619 814394301
33838 25976 690430548
19692 21674 498354122
5131 10025 350527994
21949 47668 355124869
96871 78003 869180444
68115 73706 696706591
4322 70045 880318524
...
view   save

correct output
518249578675
view   save

user output
(no output)
view   save

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
95740 71482 846654568
44131 16806 670712211
3967 49254 424174139
39369 53007 830346557
4418 78228 659410273
16217 5789 538179858
3015 75675 595730518
39197 63071 925527559
90416 41351 621837023
18944 19880 753379832
78545 59129 111771713
42276 90059 92697016
28824 25151 704906960
58221 54173 918033485
73954 70065 518414549
54067 65339 988130552
46970 24855 94876117
88140 78329 801161120
36735 81288 219036383
...
view   save

correct output
920862321580
view   save

user output
(no output)
view   save

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
79947 25489 71554257
59184 25577 328436360
82945 73554 4942918
22380 92385 874250042
3412 94292 628721882
70788 5605 692826882
96799 40481 345165540
13487 1304 203668493
17541 54712 532944388
77912 28686 959533238
37036 83500 759229572
83351 62565 136550112
9492 64706 797795297
1130 63405 727042530
6679 19880 239019578
64621 56184 409208973
35228 95875 988340080
46456 48812 745775548
8976 64911 249590152
...
view   save

correct output
399407698440
view   save

user output
(no output)
view   save

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
31139 12960 580545990
27744 95556 747296719
46969 42578 840321561
5638 28960 513805324
33834 72218 501068758
2107 70982 549265386
51704 79349 70136223
34912 51747 50717870
84117 91567 601682565
90358 83733 594109614
18731 69262 596616747
2786 96197 758321971
80096 48202 229765593
37792 41645 404273062
30940 87615 216578255
62555 96880 515513898
31038 44673 157422008
60886 92678 157493324
81428 66183 293755233
...
view   save

correct output
165235287505
view   save

user output
(no output)
view   save

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
99993 199980
1 3 1
3 2 1
1 4 1
4 2 1
1 5 1
5 2 1
1 6 1
6 2 1
1 7 1
7 2 1
1 8 1
8 2 1
1 9 1
9 2 1
1 10 1
10 2 1
1 11 1
11 2 1
1 12 1
...
view   save

correct output
2
view   save

user output
(no output)
view   save

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 149994
93867 98509 1755709
85029 99843 1347591
10305 35305 6447
75638 80585 1829972
72938 97813 1226418
50000 69871 109090
32446 50000 181762
50000 53305 149947
50000 71574 117397
97169 99889 1567712
17764 42764 9970
1 15846 746
1 14281 4995
8569 33569 1621
34101 50000 129585
1 13567 3272
50000 66735 166438
84872 97784 1096605
50000 69433 163913
...
view   save

correct output
1124960
view   save

user output
(no output)
view   save

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 200000
70413 71496 49
15963 40963 18635
81291 89420 1850028
8848 33848 17316
59455 63631 9
97284 99193 1194605
92594 93904 1417115
98921 99287 1269575
50000 73318 165218
15430 40430 12262
50000 63894 119989
87868 94144 1347091
57589 82517 1518440
50000 65836 122870
22869 29716 68
1 108 19479
90584 84782 65
1 20041 13225
18276 39479 57
...
view   save

correct output
110298
view   save

user output
(no output)
view   save