Bài 1. BESTSPOT
Bessie, luôn luôn muốn cuộc sống của mình tốt hơn , đã thấy rõ rằng cô ta thật sự rất thích ghé thăm F (1 <= F <= P) cánh đồng yêu thích F_i trong tổng số P (1 <= P <= 500;1 <= F_i <= P) cánh đồng (được đánh số từ 1-> P) thuộc sơ hữu của nông dân John.
Bessie biết rằng cô ấy có thể xác định được C (1 <= C <= 8000) con đường hai chiều (được đánh số 1 .. C) kết nối tất cả các cánh đồng trong toàn bộ nông trại. Ứng với mỗi con đường P_i là thời gian đi T_i (1 <= T_i <= 892) và nối 2 cánh đồng a_i và b_i (1 <= a_i <= P; 1 <= b_i <= P).
Bessie muốn tìm cánh đồng tốt nhất để ngủ thỏa mãn bình quân thời gian để đi đến F cánh đồng yêu thích của cô ta là nhỏ nhất.
Ví dụ, hãy xem xét một nông trang được trình bày như một bản đồ dưới đây , nơi * 'd là cách đồng được yêu thích.Các số trong ngoặc là thời gian tương ứng để di chuyển giữa 2 cánh đồng .
1 *-- [4] - 2 - [2] - 3
| |
[3] [4]
| |
4 - [3] - 5 - [1] --- 6 --- [6] --- 7 - [7] - 8 *
| | | |
[3] [2] [1] [3]
| | | |
13 * 9 - [3] - 10 *-- [1] - 11 *-- [3] - 12 *
Bảng sau đây cho thấy các khoảng cách trung bình nếu nghỉ tại các cánh đồng 4, 5, 6, 7, 9, 10, 11, và 12: 4 7 16 5 6 9 3 46/6 = 7.67 5 10 13 2 3 6 6 40/6 = 6.67 6 11 12 1 2 5 7 38/6 = 6.33 7 16 7 4 3 6 12 48/6 = 8.00 9 12 14 3 4 7 8 48/6 = 8.00 10 12 11 0 1 4 8 36/6 = 6.00 ** BEST 11 13 10 1 0 3 9 36/6 = 6.00 12 16 13 4 3 0 12 48/6 = 8.00
Kết quả tối ưu là cánh đồng 10
Dữ liệu
-
Dòng 1: 3 số nguyên P,F,C
-
Dòng 2..F+1: Dòng i+2 chứa 1 số Nguyên F_i
-
Dòng F+2..C+F+1 : Mỗi dòng chứa 3 số Nguyên a_i, b_i, F_i mô tả 1 con đường 2 chiều là thời gian di chuyển giữa chúng.
Kết quả
Gồm 1 dòng duy nhất là cánh đồng được chọn . nếu có nhiều kết quả , chọn cánh đồng có chỉ số nhỏ nhất !
Ví dụ
Dữ liệu
13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7
|
Kết quả
10
|
Chương trình tham khảo:
const
fi='';
fo='';
maxn=1000;
maxm=100000;
vc=1000000000;
var
f,g:text;
free:array[-1..maxn+4] of boolean;
head,d:array[-1..maxn+4] of longint;
adj,adjcost,dau,cuoi,cost,heap,pos:array[-1..maxm+4] of longint;
p,fy,c,test,nheap:longint;
cdyt:array[-1..maxn+4] of longint;
best:real;
vtbest:longint;
procedure doc;
var i,j:longint;
begin
assign(f,fi);
reset(f);
Readln(f,p,fy,c);
for i:= 1 to fy do readln(f,cdyt[i]);
fillchar(head,sizeof(head),0);
for i:=1 to c do
begin
Readln(f,dau[i],cuoi[i],cost[i]);
inc(head[dau[i]]);
inc(head[cuoi[i]]);
end;
for i:=2 to p do head[i]:=head[i-1]+head[i];
head[p+1]:=head[p];
for i:=1 to c do
begin
adj[head[dau[i]]]:=cuoi[i];
adjcost[head[dau[i]]]:=cost[i];
dec(head[dau[i]]);
adj[head[cuoi[i]]]:=dau[i];
adjcost[head[cuoi[i]]]:=cost[i];
dec(head[cuoi[i]]);
end;
close(f);
end;
procedure update(v:longint);
var child,parent:longint;
begin
child:=pos[v];
if child=0 then
begin
inc(nheap);
child:=nheap;
end;
parent:=child div 2;
while (parent>0) and (d[heap[parent]]>d[v]) do
begin
heap[child]:=heap[parent];
pos[heap[child]]:=child;
child:=parent;
parent:=child div 2;
end;
heap[child]:=v;
pos[v]:=child;
end;
function pop:longint;
var r,v,c:longint;
begin
pop:=heap[1];
v:=heap[nheap];
dec(nheap);
r:=1;
while r*2<=nheap do
begin
c:=r*2;
if (cif d[v]<=d[heap[c]] then break;
heap[r]:=heap[c];
pos[heap[r]]:=r;
r:=c;
end;
heap[r]:=v;
pos[v]:=r;
end;
procedure disktra(v:longint);
var i,j,u,min,z:longint;
begin
for i:=1 to p do d[i]:=vc;
min:=vc;
d[v]:=0;
fillchar(free,sizeof(free),true);
fillchar(pos,sizeof(pos),0);
fillchar(heap,sizeof(heap),0);
nheap:=0;
update(v);
repeat
u:=pop;
if u=0 then break;
free[u]:=false;
for i:=head[u]+1 to head[u+1] do
begin
if free[adj[i]] then
if d[adj[i]]>d[u]+adjcost[i] then
begin
d[adj[i]]:=d[u]+adjcost[i];
update(adj[i]);
end;
end
until nheap=0;
end;
function tbtg:real;
var i:longint;
sumtg:real;
begin
sumtg:=0;
for i:= 1 to fy do sumtg:=sumtg+d[cdyt[i]];
tbtg:=sumtg/fy;
end;
procedure process;
var i:longint;
tam:real;
begin
vtbest:=0;
best:=1000000000000;
for i:=1 to p do
begin
disktra(i);
tam:=tbtg;
if(best>tam) then
begin
best:=tam;
vtbest:=i;
end;
end;
end;
procedure ctchinh;
var i,j:longint;
begin
assign(g,fo);
rewrite(g);
doc;
process;
write(g,vtbest);
close(g);
end;
begin
ctchinh;
end.
|
Bài 2. BINLADEN
Trùm khủng bố Bin Laden trốn trong 1 căn hầm được đào sâu xuống mặt đất M tầng, mỗi tầng có N phòng. Các phòng được ngăn cách bằng các cửa rất khó phá. Các phòng có cửa xuống phòng ngay phía dưới và 2 phòng ở 2 bên. Từ trên mặt đất có N cửa xuống N phòng tầng -1. Bin Laden ở tầng dưới cùng (tầng -M) phòng thứ N (phòng ở bên phải nhất). Mỗi cửa được làm bằng một kim loại khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.
Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát mất.
Dữ liệu
-
Dòng 1 ghi M và N
-
Dòng 2 đến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi phí để phá cửa.
Kết quả
Ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden
Ví dụ
Dữ liệu
4 2
99 10
1
10 99
1
99 10
1
10 99
1
Kết quả
44
+--99--+--10--+
| | |
| 1 |
| | |
+--10--+--99--+
| | |
| 1 |
| | |
+--99--+--10--+
| | |
| 1 |
| | |
+--10--+--99--+
| | |
| 1 |
| | |
+------+------+
Đi theo đường zigzac
Giới hạn
-
1 <= M <= 2222
-
1 <= N <= 10
-
Chi phí của các cánh cửa thuộc [0, 1000].
Chương trình tham khảo :
const
fi=''; fo='';
maxn=22231; vc=100000000; maxm=244423;
var n,m,nheap,n1: longint; f: text;
h,heap,d: array [-1..maxn+4] of longint;
dd: array [-1..maxn+4] of boolean;
adj,adjcost,cost,pos: array [-1..maxm+4] of longint;
procedure doc;
var i,j,d1,d2,c,gt: longint;
dau,cuoi: array [-1..maxm+4] of longint;
begin
fillchar(h,sizeof(h),0);
assign(f,fi); reset(f);
readln(f,m,n);
d1:=1; d2:=d1+n; c:=0;
for i:=1 to m do
begin
for j:=0 to n-1 do
begin
read(f,gt); inc(c);
dau[c]:=d1+j; cuoi[c]:=d2+j;
cost[c]:=gt;
inc(h[dau[c]]); inc(h[cuoi[c]]);
end;
readln(f);
for j:=0 to n-2 do
begin
read(f,gt); inc(c);
dau[c]:=d2+j; cuoi[c]:=d2+1+j;
cost[c]:=gt;
inc(h[dau[c]]); inc(h[cuoi[c]]);
end;
readln(f);
d1:=d2; d2:=d1+n;
end;
n1:=n; n:=n*m+n; m:=c;
for i:=2 to n do h[i]:=h[i-1]+h[i];
h[n+1]:=h[n];
for i:=1 to m do
begin
adj[h[dau[i]]]:=cuoi[i];
adjcost[h[dau[i]]]:=cost[i];
dec(h[dau[i]]);
adj[h[cuoi[i]]]:=dau[i];
adjcost[h[cuoi[i]]]:=cost[i];
dec(h[cuoi[i]]);
end;
close(f);
end;
procedure ktao(s: longint);
var i: longint;
begin
fillchar(dd,sizeof(dd),false);
fillchar(pos,sizeof(pos),0);
fillchar(heap,sizeof(heap),0);
for i:=1 to n do d[i]:=vc;
d[s]:=0;
nheap:=0;
end;
procedure update(v: longint);
var cha,con: longint;
begin
con:=pos[v];
if con=0 then
begin
inc(nheap);
con:=nheap;
end;
cha:=con div 2;
while (cha>0) and (d[heap[cha]]>d[v]) do
begin
heap[con]:=heap[cha];
pos[heap[con]]:=con;
con:=cha;
cha:=con div 2;
end;
heap[con]:=v;
pos[v]:=con;
end;
function pop: longint;
var v,cha,con: longint;
begin
pop:=heap[1];
v:=heap[nheap]; dec(nheap);
cha:=1;
while 2*cha<=nheap do
begin
con:=2*cha;
if (cond[heap[con+1]]) then inc(con);
if d[heap[con]]>=d[v] then break;
heap[cha]:=heap[con];
pos[heap[cha]]:=cha;
cha:=con;
end;
heap[cha]:=v;
pos[v]:=cha;
end;
procedure xuli(s: longint);
var i,u: longint;
begin
ktao(s); update(s);
repeat
u:=pop;
if u=0 then exit;
dd[u]:=true;
for i:=h[u]+1 to h[u+1] do
if not(dd[adj[i]]) and (d[adj[i]]>d[u]+adjcost[i]) then
begin
d[adj[i]]:=d[u]+adjcost[i];
update(adj[i]);
end;
until nheap=0;
end;
procedure ghi;
var i,min: longint;
begin
min:=vc;
for i:=1 to n1 do
begin
xuli(i);
if d[n]
min:=d[n];
end;
assign(f,fo); rewrite(f);
writeln(f,min);
close(f);
end;
BEGIN
doc;
ghi;
END.
|
Bài 3. TOURS13
Công ty du lịch X có dự án tổ chức các hành trình du lịch trong vùng lãnh thổ gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m tuyến đường một chiều khác nhau, tuyến đường thứ j ( j = 1, 2, 3, …, m) cho phép đi từ địa diểm uj đến dịa diểm vj với chi phí đi lại là một số nguyên dương c(uj, vj). Vấn đề đặt ra cho công ty là xây dựng các hành trình du lịch cho mỗi điểm du lịch. Một hành trình du lịch cho địa điểm du lịch i phải được xây dựng sao cho xuất phát từ địa điểm i đi qua một số địa điểm khác rồi quay lại địa điểm xấu phát i với tổng chi phí (được tính như là tổng chi phí của các tuyến đường mà hành trình đi qua) nhỏ nhất.
Input
Dòng đầu tiên số T là số lượng bộ dữ liệu. tiếp đến là T nhóm dòng, mỗi dòng cho thông tin về một bộ dữ liệu theo khuôn dạng sau :
-
Dòng thứ nhất chứa 2 số nguyên dương n, m
-
Dòng thứ j trong số m dòng tiếp theo chứa ba số nguyên duong uj, vj, c(uj, vj) cho biết thông tin về tuyến đường thứ j. Giả thiết là uj ≠ vj; c(uj, vj) < 10^6; j = 1, 2, …, m
Output
Gồm T nhóm dòng tương ứng với T bộ test vào, mỗi nhóm dòng gồm n dòng, dòng thứ i ghi chi phí của hành trình du lịch cho địa điểm i. Qui ước: Ghi số -1 trên dòng i nếu không tìm được hành trình du lịch cho địa điểm i thỏa mãn yêu cầu đặt ra
Example
Input:
1
6 8
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7
Output:
11
11
6
11
6
-1
Ràng buộc:
-
Có 30% số test tương ứng với 30% số điểm của bài có n <= 20.
-
Có 30% số test tương ứng với 30% số điểm của bài có 20 < n <= 100, m <= 104.
-
Có 40% số test tương ứng với 30% số điểm của bài có 100 < n <= 103, m <= 105
Chương trình tham khảo
const
fi='';
fo='';
maxn=1000;
maxm=100000;
vc=2*1000000000;
var f,g:text;
free:array[-1..maxn+4] of boolean;
head,d:array[-1..maxn+4] of longint;
adj,adjcost,dau,cuoi,cost,heap,pos:array[-1..maxm+4] of longint;
n,m,test,nheap:longint;
procedure doc;
var i,j:longint;
begin
Readln(f,n,m);
fillchar(head,sizeof(head),0);
for i:=1 to m do
begin
Readln(f,dau[i],cuoi[i],cost[i]);
inc(head[dau[i]]);
end;
for i:=2 to n do head[i]:=head[i-1]+head[i];
head[n+1]:=head[n];
for i:=1 to m do
begin
adj[head[dau[i]]]:=cuoi[i];
adjcost[head[dau[i]]]:=cost[i];
dec(head[dau[i]]);
end;
end;
procedure update(v:longint);
var child,parent:longint;
begin
child:=pos[v];
if child=0 then
begin
inc(nheap);
child:=nheap;
end;
parent:=child div 2;
while (parent>0) and (d[heap[parent]]>d[v]) do
begin
heap[child]:=heap[parent];
pos[heap[child]]:=child;
child:=parent;
parent:=child div 2;
end;
heap[child]:=v;
pos[v]:=child;
end;
function pop:longint;
var r,v,c:longint;
begin
pop:=heap[1];
v:=heap[nheap];
dec(nheap);
r:=1;
while r*2<=nheap do
begin
c:=r*2;
if (c
if d[v]<=d[heap[c]] then break;
heap[r]:=heap[c];
pos[heap[r]]:=r;
r:=c;
end;
heap[r]:=v;
pos[v]:=r;
end;
procedure disktra(v:longint);
var i,j,u,min,z:longint;
begin
for i:=1 to n do
d[i]:=vc;
min:=vc;
d[v]:=0;
fillchar(free,sizeof(free),true);
fillchar(pos,sizeof(pos),0);
fillchar(heap,sizeof(heap),0);
nheap:=0;
update(v);
repeat
u:=pop;
if u=0 then break;
free[u]:=false;
for i:=head[u]+1 to head[u+1] do
if adj[i]<>v then
begin
if free[adj[i]] then
if d[adj[i]]>d[u]+adjcost[i] then
begin
d[adj[i]]:=d[u]+adjcost[i];
update(adj[i]);
end;
end
else
if adj[i]=v then
begin
if d[u]+adjcost[i]
min:=d[u]+adjcost[i];
end;
until nheap=0;
if min=vc then writeln(g,'-1')
else
writeln(g,min);
end;
procedure process;
var i:longint;
begin
for i:=1 to n do
disktra(i);
end;
procedure ctchinh;
var i,j:longint;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
Readln(f,test);
for i:=1 to test do
begin
doc;
process;
end;
close(f);
close(g);
end;
begin
ctchinh;
end.
|
Bài 4. ROADS
Có N thành phố 1..N nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố 1. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố N, biết rằng Bob chỉ có số tiền có hạn là K mà thôi.
Dữ liệu
Dòng đầu tiên ghi t là số test. Với mỗi test, dòng đầu ghi K (0 ≤ K ≤ 10000). Dòng 2 ghi N, 2 ≤ N ≤ 100. Dòng 3 ghi R, 1 ≤ R ≤ 10000 là số đường nối. Mỗi dòng trong N dòng sau ghi 4 số nguyên S, D, L, T mô tả một con đường nối giữa S và D với độ dài L ( 1 ≤ L ≤ 100) và chi phí T (0 ≤ T ≤ 100). Lưu ý có thể có nhiều con đường nối giữa hai thành phố.
Kết quả
Với mỗi test, in ra độ dài đường đi ngắn nhất từ 1 đến N mà tổng chi phí không quá K. Nếu không tồn tại, in ra -1.
Ví dụ
Dữ liệu
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
Kết quả
11
-1
Chương trình tham khảo:
const fi = '';
fo = '';
maxn = 100;
maxm =10000;
vc = 10000000;
type
m2 =array[1..maxn, 1..maxn] of longint;
m1= array[1..maxn] of longint;
var
head,d:array[-1..maxn+4] of longint;
adj,adjcost,adjdist, dau,cuoi,cost1,dist1:array[-1..maxm+4] of longint;
dd : array[1..maxn] of boolean;
cost, dist :m2;
mincost, mindist :m1 ;
k : longint;
sl,t,n : longint;
best : longint;
f,g : text;
tb : longint;
procedure doc;
var i, r, u, v: longint;
begin
readln(f, k); {so tien cua Bob}
readln(f, n); {so thanh pho}
readln(f, r); {so con duong}
fillchar(head,sizeof(head),0);
for i:=1 to r do
begin
Readln(f,dau[i],cuoi[i],dist1[i], cost1[i]);
inc(head[dau[i]]);
end;
for i:=2 to n do head[i]:=head[i-1]+head[i];
head[n+1]:=head[n];
for u:=1 to n do
for v:=1 to n do
begin
cost[u, v]:=vc;
dist[u, v]:=vc;
end;
for i:=1 to r do
begin
adj[head[dau[i]]]:=cuoi[i];
adjdist[head[dau[i]]]:=dist1[i];
adjcost[head[dau[i]]]:=cost1[i];
dec(head[dau[i]]);
if dist1[i] < dist[dau[i], cuoi[i]] then
dist[dau[i], cuoi[i]]:=dist1[i];
if cost1[i]< cost[dau[i], cuoi[i]] then
cost[dau[i], cuoi[i]]:=cost1[i];
end;
end;
{dist[i] la khoang cach be nhat tu i den n}
procedure dijkstra(var a : m2; var dist : m1);
var chua : array[1..maxn] of boolean;
min : longint;
i, j, u : longint;
begin
fillchar(chua, sizeof(chua), true);
for i:=1 to n do dist[i]:=vc;
dist[n]:=0;
repeat
min:=vc;
u:=0;
for j:=1 to n do
if chua[j] and (dist[j] < min) then
begin
min:=dist[j];
u:=j;
end;
if(u=0) then break;
chua[u]:=false;
for j:=1 to n do
if chua[j] and (a[j, u] + dist[u] < dist[j]) then
dist[j]:=dist[u] + a[j, u];
until(false);
end;
procedure try(last : longint; l, t : longint);
var i:longint;
begin
if (l + mindist[last] >= best) or (t + mincost[last] > k) then exit;
if last = n then
begin
best:=l; exit;
end;
for i:=head[last]+1 to head[last+1] do
begin
if not dd[adj[i]] then {thanh pho v chua qua}
begin
dd[adj[i]]:=true;
try(adj[i], l+adjdist[i] , t+adjcost[i] );
dd[adj[i]]:=false;
end;
end;
end;
procedure process;
begin
dijkstra(cost, mincost);
dijkstra(dist, mindist);
best:=vc;
fillchar(dd, sizeof(dd), false);
try(1, 0, 0);
end;
procedure done;
begin
if best = vc then
writeln(g, -1)
else
writeln(g, best);
end;
BEGIN
assign(g, fo); rewrite(g);
assign(f, fi); reset(f);
readln(f,t);
for sl:=1 to t do
begin
doc;
process;
done;
end;
close(f);
close(g);
END.
|
Bài 5. QBSCHOOL
Ngày 27/11 tới là ngày tổ chức thi học kỳ I ở trường ĐH BK. Là sinh viên năm thứ nhất, Hiếu không muốn vì đi muộn mà gặp trục trặc ở phòng thi nên đã chuẩn bị khá kỹ càng. Chỉ còn lại một công việc khá gay go là Hiếu không biết đi đường nào tới trường là nhanh nhất.
Thường ngày Hiếu không quan tâm tới vấn đề này lắm cho nên bây giờ Hiếu không biết phải làm sao cả . Bản đồ thành phố là gồm có N nút giao thông và M con đường nối các nút giao thông này. Có 2 loại con đường là đường 1 chiều và đường 2 chiều. Độ dài của mỗi con đường là một số nguyên dương.
Nhà Hiếu ở nút giao thông 1 còn trường ĐH BK ở nút giao thông N. Vì một lộ trình đường đi từ nhà Hiếu tới trường có thể gặp nhiều yếu tố khác như là gặp nhiều đèn đỏ , đi qua công trường xây dựng, ... phải giảm tốc độ cho nên Hiếu muốn biết là có tất cả bao nhiêu lộ trình ngắn nhất đi từ nhà tới trường. Bạn hãy lập trình giúp Hiếu giải quyết bài toán khó này.
Input
Dòng thứ nhất ghi hai số nguyên N và M.
M dòng tiếp theo, mỗi dòng ghi 4 số nguyên dương K, U, V, L. Trong đó:
K = 1 có nghĩa là có đường đi một chiều từ U đến V với độ dài L.
K = 2 có nghìa là có đường đi hai chiều giữa U và V với độ dài L.
Output
Ghi hai số là độ dài đường đi ngắn nhấn và số lượng đường đi ngắn nhất. Biết rằng số lượng đường đi ngắn nhất không vượt quá phạm vì int64 trong pascal hay long long trong C++.
Example
Input:
3 2
1 1 2 3
2 2 3 1
Output:
4 1
Giới hạn:
1 ≤ N ≤ 5000
1 ≤ M ≤ 20000
Độ dài các con đường ≤ 32000
procedure disktra;
var i,j,u,min,z:longint;
begin
fillchar(pos,sizeof(pos),0);
fillchar(heap,sizeof(heap),0);
for i:=1 to p do f1[i]:='';
f1[1]:='1';
for i:=1 to p do d[i]:=vc;
min:=vc;
d[1]:=0;
nheap:=0;
update(1);
repeat
u:=pop;
if u=0 then break;
free[u]:=false;
for i:=head[u]+1 to head[u+1] do
begin
if free[adj[i]] then
if d[adj[i]] > d[u]+adjcost[i] then
begin
d[adj[i]]:=d[u]+adjcost[i];
update(adj[i]);
f1[adj[i]]:=f1[u];
end
else
if d[adj[i]] = d[u]+adjcost[i] then f1[adj[i]]:= cong(f1[adj[i]] , f1[u]);
end
until nheap=0;
end;
Chia sẻ với bạn bè của bạn: |