Cele mai bune solutii
pentru problema "Turism"
(ziua2, problema6)
Punctaj Maxim : 50 puncte
Solutii :
Ileana Ioana - Alba
Comisia Centrala
Fisierele de teste
Program realizat de elevul Ileana Ioana - rezultat final : premiu III - 111 puncte
program ayr;
uses crt;
const inf=maxint div 2;
var dr,nrd:array[1..100] of integer;
a:array[1..100,1..100] of integer;
n,i,j,k,p,s,pk:integer;
f:text;
marcat:array[1..100] of boolean;
procedure citire;
begin
assign(f,'turist.in');
reset(f);
readln(f,n);
readln(f,p,s);
for i:=1 to n do
for j:=1 to n do a[i,j]:=inf;
while not seekeof(f) do
readln(f,i,j,a[i,j]);
close(f);
end;
procedure senna;
begin
marcat[p]:=true;
nrd[p]:=1;
for i:=1 to n do begin
if a[p,i]<>inf then nrd[i]:=1
else nrd[i]:=0;
dr[i]:=a[p,i];
end;
repeat
k:=0;
pk:=inf;
for i:=1 to n do if (not marcat[i]) and (dr[i]<pk) then begin
pk:=dr[i];
k:=i;
end;
marcat[k]:=true;
for i:=1 to n do if not (marcat[i]) then
if dr[k]+a[k,i]<dr[i] then begin
nrd[i]:=nrd[k];
dr[i]:=dr[k]+a[k,i];
end
else if dr[k]+a[k,i]=dr[i] then
nrd[i]:=nrd[i]+nrd[k];
until k=s;
assign(f,'turist.out');
rewrite(f);
writeln(f,dr[s],' ',nrd[s]);
close(f);
end;
begin
citire;
senna;
end.
Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica
{Rezolvare propusa de comisie - implementata de Clara Ionescu}
Program drum;
type matrice=array[1..100,1..100] of integer;
var c,d:matrice;
i,j,n,h,v1,v2,k,nr,v11,v22: integer;
fi,fo:text;
procedure init;
var i,j,k,cst:integer;
begin
assign(fi,'turist.in');reset(fi);
readln(fi,n);
readln(fi,v11,v22);
for i:=1 to n do
begin
c[i,i]:=0; d[i,i]:=0;
for j:=1 to i-1 do
begin
c[i,j]:=0; d[i,j]:=0;
c[j,i]:=0; d[j,i]:=0;
end;
end;
while not seekeof(fi) do
begin readln(fi,v1,v2,cst);
d[v1,v2]:=cst;
c[v1,v2]:=1;
end;
close(fi);
end;
Begin
init;
assign(fo,'turist.out'); rewrite(fo);
h:=0;
for k:=1 to n do
begin
for i:=1 to n do
if d[i,k]>0
then
for j:=1 to n do
if d[k,j]>0
then
if d[i,j]=0
then
begin
c[i,j]:=c[i,k]*c[k,j];
d[i,j]:=d[i,k]+d[k,j];
end
else
if d[i,j]=d[i,k]+d[k,j]
then c[i,j]:=c[i,j]+c[i,k]*c[k,j]
else
if d[i,j]>d[i,k]+d[k,j]
then
begin
c[i,j]:=c[i,k]*c[k,j];
d[i,j]:=d[i,k]+d[k,j];
end;
end;
writeln(fo,d[v11,v22],' ',c[v11,v22]);
close(fo)
end.
Fisierele de teste :
Test 1 :
6
1 3
1 2 1
2 3 1
1 5 1
1 6 2
2 6 1
5 6 1
5 4 1
6 4 1
6 3 1
4 3 1
Test 3 :
12
1 12
1 2 10
1 5 3
1 8 5
2 3 3
5 6 10
8 9 9
3 4 5
3 11 7
6 7 4
9 11 6
9 12 16
9 10 25
10 11 20
11 12 10
4 11 2
4 12 12
7 11 3
Test 4 :
9
1 8
1 2 5
1 3 7
1 5 4
2 4 5
3 4 3
5 4 6
4 6 10
6 7 5
6 9 2
7 8 5
9 8 8
Test 5 :
10
1 10
1 2 5
1 3 6
1 4 7
1 5 5
1 6 6
1 7 7
2 8 5
2 9 6
3 10 7
4 5 2
5 6 3
6 7 2
Test 6 :
40
1 20
1 2 14
2 3 12
3 4 19
4 5 12
5 6 20
6 7 3
7 8 1
8 9 19
9 10 8
10 11 8
11 12 6
12 13 1
13 14 14
14 15 18
15 16 15
16 17 5
17 18 7
18 19 14
19 20 18
1 8 87
8 10 27
10 20 100
Test 7 :
100
13 49
72 86 96
11 65 4
39 41 24
45 48 47
11 26 71
68 95 26
2 66 44
57 58 21
12 88 94
2 57 23
29 69 16
25 75 63
33 52 41
49 61 69
30 96 51
22 32 18
5 8 42
31 59 83
24 56 83
7 76 80
69 81 86
19 38 31
35 91 100
39 79 98
67 88 64
7 72 87
19 77 5
5 67 32
9 41 29
6 53 10
18 67 21
73 99 27
47 88 96
9 33 52
32 37 90
8 71 42
38 45 94
41 74 66
26 36 40
19 72 74
13 49 52
18 46 59
8 48 85
46 91 62
17 86 27
52 87 81
6 49 64
62 72 21
11 30 43
98 99 89
40 96 50
59 65 58
54 65 5
57 95 65
13 43 50
43 49 2
75 89 58
18 46 61
49 81 79
10 16 40
7 74 15
2 12 66
92 98 61
58 79 30
21 64 69
35 93 30
11 35 82
18 52 12
70 71 12
21 50 61
54 100 43
23 70 68
58 69 41
50 77 53
11 20 3
12 97 91
4 26 97
38 63 56
20 72 50
55 73 84
63 65 27
38 57 41
1 6 46
34 87 51
64 68 90
40 52 96
13 81 64
31 94 97
3 26 27
71 78 98
11 24 46
44 61 71
30 96 88
2 27 98
18 23 27
9 41 78
38 74 66
41 58 6
26 94 35
63 95 15
30 76 16
Test 8 :
30
1 30
1 2 1
2 3 1
3 8 1
8 13 1
1 5 1
5 7 1
7 8 1
8 12 1
12 17 1
13 17 1
23 26 1
25 26 1
24 25 1
20 24 1
17 20 1
16 25 2
11 16 2
7 11 2
5 7 1
1 5 1
1 4 1
4 6 1
6 9 1
9 14 1
14 18 1
18 21 1
21 22 1
22 23 1
25 26 1
6 10 1
10 15 1
15 19 1
19 23 3
26 27 1
27 28 1
28 29 1
29 30 10
Test 9 :
60
1 60
1 2 1
2 3 1
3 8 1
8 13 1
1 5 1
5 7 1
7 8 1
8 12 1
12 17 1
13 17 1
25 26 1
24 25 1
20 24 1
17 20 1
16 25 2
11 16 2
7 11 2
5 7 1
1 5 1
1 4 1
4 6 1
6 9 1
9 14 1
14 18 1
18 21 1
21 22 1
22 23 1
23 26 1
25 26 1
6 10 1
10 15 1
15 19 1
19 23 3
26 27 1
27 28 1
28 29 1
29 30 10
30 31 1
31 32 1
32 33 1
33 38 1
38 43 1
31 35 1
35 37 1
37 38 1
38 42 1
42 47 1
43 47 1
55 56 1
54 55 1
50 54 1
47 50 1
46 55 2
41 46 2
37 41 2
35 37 1
31 35 1
31 34 1
34 36 1
36 39 1
39 44 1
44 48 1
48 51 1
51 52 1
52 53 1
53 56 1
55 56 1
36 40 1
40 45 1
45 49 1
49 53 3
56 57 1
57 58 1
58 59 1
59 60 10
Test 10 :
100
7 77
48 4 38
23 43 84
17 39 51
7 12 45
12 67 19
28 4 41
11 52 94
26 13 11
24 74 35
87 41 77
56 76 44
58 50 48
49 35 59
27 45 19
17 93 88
28 38 10
56 17 58
1 30 83
79 83 7
91 22 8
61 1 50
32 65 25
74 84 88
66 33 14
29 63 13
27 25 49
62 28 5
40 90 26
53 99 14
97 21 18
70 79 98
33 28 92
5 15 22
92 7 81
45 21 57
16 40 67
93 51 42
14 32 2
23 25 64
40 27 36
44 16 41
31 79 17
14 98 24
92 93 39
23 61 97
60 95 44
18 33 40
36 89 63
72 9 18
72 76 47
45 58 10
37 51 51
54 40 74
32 75 56
90 69 92
53 28 52
39 80 89
81 47 39
61 19 21
68 16 87
80 30 91
8 49 56
62 14 70
65 31 35
53 39 46
88 52 71
93 24 96
92 96 45
73 10 89
73 33 78
95 23 1
58 10 35
95 92 36
64 58 73
74 4 15
55 45 33
69 96 69
100 82 90
71 40 64
7 50 50
50 77 50
9 77 69
16 31 82
49 4 65
62 93 90
94 35 26
27 62 63
82 77 13
9 70 43
66 57 4
17 24 44
51 50 14
94 7 37
100 55 68
77 54 29
32 88 58
8 5 71
37 34 65
8 13 7
45 77 50
84 11 89
12 45 5
73 70 31
80 44 43
39 19 82