// các số luỹ thừa của 10: 1, 10, 100, 1000, 10000, ...llipower_of_ten=1;// giới hạn trên của phạm vi đang xét: 9, 99, 999, 9999, ...llibound;// số chữ số trong phạm vi đang xét: 1, 2, 3, 4, ...llinumber_of_digits=1;// số lượng số trong phạm vi đang xétlliamount;
# các số luỹ thừa của 10: 1, 10, 100, 1000, 10000, ...power_of_ten=1# giới hạn trên của phạm vi đang xét: 9, 99, 999, 9999, ...bound=0# số chữ số trong phạm vi đang xét: 1, 2, 3, 4, ...number_of_digits=1# số lượng số trong phạm vi đang xétamount=0
2. Xử lý lần lượt từng phạm vi
Áp dụng vòng lặp while để xử lý từng phạm vi. Trong mỗi phạm vi, cần chú ý giá trị của n so với giới hạn trên bound (là số kết thúc của mỗi phạm vi).
while(true){// Tính giới hạn trên của phạm vi đang xét: 9, 99, 999, 9999, ...bound=power_of_ten*10-1;// So sánh n và giới hạn trênif(n>=bound){// Tính số lượng số trong phạm vi đang xét: 9, 90, 900, 9000, ...amount=9*power_of_ten;// Lấy số lượng số x số chữ số, rồi cộng dồn vào kết quảtotal_digits+=amount*number_of_digits;}else{// Tính số lượng số trong phạm vi đang xétamount=n-power_of_ten+1;// Lấy số lượng số x số chữ số, rồi cộng dồn vào kết quảtotal_digits+=amount*number_of_digits;// Thoát vòng lặp, kết thúc chương trìnhbreak;}// Tăng số chữ số để xét phạm vi tiếp theonumber_of_digits+=1;// Nhân thêm 10power_of_ten*=10;// Điều kiện dừng vòng lặpif(power_of_ten>n)break;}
while(True):# Tính giới hạn trên của phạm vi đang xét: 9, 99, 999, 9999, ...bound=power_of_ten*10-1# So sánh n và giới hạn trênifn>=bound:# Tính số lượng số trong phạm vi đang xét: 9, 90, 900, 9000, ...amount=9*power_of_ten# Lấy số lượng số x số chữ số, rồi cộng dồn vào kết quảtotal_digits+=amount*number_of_digitselse:# Tính số lượng số trong phạm vi đang xét: 9, 90, 900, 9000, ...amount=n-power_of_ten+1# Lấy số lượng số x số chữ số, rồi cộng dồn vào kết quảtotal_digits+=amount*number_of_digits# Thoát vòng lặp, kết thúc chương trìnhbreak# Tăng số chữ số để xét phạm vi tiếp theonumber_of_digits+=1# Nhân thêm 10power_of_ten*=10# Điều kiện dừng vòng lặpifpower_of_ten>n:break
Một mạng lưới giao thông gồm \(N\) nút được đánh số \(1..N\), và \(M\) con đường hai chiều nối các các nút với nhau.
Mỗi nút giao thông \(I\) có một chi phí hành trình là \(T_i\). Chi phí lưu thông trên mỗi con đường nối hai nút khác nhau \(I\) và \(K\) là \(L_{ik} = L_{ki}\).
Một người muốn di chuyển từ nút giao thông này đến nút giao thông khác sẽ chịu chi phí bằng tổng chi phí lưu thông của các con đường đã đi qua, cộng với chi phí hành trình lớn nhất trong số các nút giao thông đã gặp. Chi phí này quá lớn đối với một người, vì vậy họ phải tính toán trước chi phí phải trả ít nhất khi di chuyển để quyết định xem có nên đi hay không.
Yêu cầu: Cho nhu cầu di chuyển giữa \(R\) cặp nút. Hãy tính chi phí nhỏ nhất phải trả cho việc di chuyển giữa mỗi cặp nút giao thông này.
Dữ liệu vào: CHIPHI.INP
Dòng đầu tiên gồm 3 số nguyên: \(N (1 \le N \le 250)\), \(M (1 \le M \le 10000)\) và \(R (1 \le R \le 10000)\).
\(N\) dòng tiếp theo, mỗi dòng ghi một số nguyên \(T (1 \le T \le 100000)\) tương ứng chi phí hành trình của một nút giao thông \(1..N\).
\(M\) dòng tiếp theo mỗi dòng ghi 3 số nguyên dương: \(I, K, L (I \neq K, 1 \le L \le 100000)\) biểu diễn việc di chuyển trên con đường hai chiều nối hai nút giao thông \(I\) và \(K\), sẽ mất chi phí lưu thông là \(L\).
\(R\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên: \(U, V (U \neq V)\) biểu diễn nhu cầu di chuyển từ nút giao thông U đến nút giao thông V.
Kết quả: CHIPHI.OUT
Gồm \(R\) dòng, mỗi dòng là một số nguyên tương ứng với chi phí nhỏ nhất khi di chuyển giữa một cặp nút.
Nhu cầu di chuyển giữa hai cặp nút: từ nút 1 đến nút 4, từ nút 2 đến nút 3.
Cách tính chi phí nhỏ nhất như sau:
Để đi từ nút 1 đến nút 4 mất chi phí ít nhất thì cần phải đi qua các nút theo trình tự: \(1 - 3 - 5 - 4\). Chi phí là \((L_{13} + L_{53} + L_{54}) + max\{T_1, T_2, T_3, T_4\}\), tương ứng \((2 + 1 + 1) + 4 = 8\).
Để đi từ nút 2 đến nút 3 mất chi phí ít nhất thì cần phải đi qua các nút theo trình tự: \(2 - 5- 3\). Chi phí là \((L_{25} + L_{53}) + max\{T_2, T_5, T_3\}\), tương ứng \((3 + 1) + 5 = 9\).
Áp dụng thuật toán Floyd-Warshall vì thuật toán này có thể tìm được chi phí nhỏ nhất giữa các cặp nút, giúp nhanh chóng trả lời một loạt các truy vấn (một loạt cặp nút) mà không mất công chạy lại thuật toán cho từng cặp.
typedeflonglongintlli;constlliINF=1e18;structnode{intid;inttravel_cost;};// số nút, số nút, số truy vấnintn,m,r;// Mảng lưu nút và chi phí hành trình Tvector<lli>T;// Mảng lưu nút và chi phí hành trình T để tìm giá trị lớn nhấtvector<node>nodes;// Mảng lưu chi phí lưu thông L giữa hai nútvector<vector<lli>>L;// Mảng lưu các truy vấn (là các cặp nút)vector<pair<int,int>>queries;// mảng lưu kết quả tổng chi phí nhỏ nhất giữa hai cặp nút (dành cho các truy vấn)vector<vector<lli>>results;
INF=int(1e18)classnode:def__init__(self,id,travel_cost):self.id=idself.travel_cost=travel_cost# số nút, số nút, số truy vấnn=m=r=0# Mảng lưu nút và chi phí hành trình TT=[]# Mảng lưu nút và chi phí hành trình T để tìm giá trị lớn nhấtnodes=[]# Mảng lưu chi phí lưu thông L giữa hai nútL=[]# Mảng lưu các truy vấn (là các cặp nút)queries=[]# mảng lưu kết quả tổng chi phí nhỏ nhất giữa hai cặp nút (dành cho các truy vấn)results=[]
cin>>n>>m>>r;// Đọc chi phí hành trình TT.resize(n+1);nodes.resize(n);for(inti=0;i<n;++i){nodes[i].id=i+1;cin>>nodes[i].travel_cost;T[i+1]=nodes[i].travel_cost;}// Khởi tạo mảng chi phí lưu thông LL.resize(n+1,vector<lli>(n+1,INF));// Khởi tạo mảng kết quảresults.resize(n+1,vector<lli>(n+1,INF));// Khởi tạo cho trường hợp một nút đi đến chính nófor(inti=1;i<n+1;++i){L[i][i]=0;results[i][i]=T[i];}// Đọc chi phí lưu thông l giữa hai nút i và kinti,k;llil,initial_total_cost;for(intu=0;u<m;++u){cin>>i>>k>>l;L[i][k]=l;L[k][i]=l;// Tạm tính tổng chi phí ban đầu initial_total_cost=l+max(T[i],T[k]);results[i][k]=initial_total_cost;results[k][i]=initial_total_cost;}// Khởi tạo mảng các truy vấnqueries.resize(r);// Đọc các cặp nút cần truy vấnintu_query,v_query;for(inti=0;i<r;++i){cin>>u_query>>v_query;queries[i]={u_query,v_query};}
withopen(input_file,'r')asf:n,m,r=map(int,f.readline().split())# Đọc chi phí hành trình TT=[0]*(n+1)nodes=[node(0,0)for_inrange(n)]foriinrange(n):nodes[i].id=i+1nodes[i].travel_cost=int(f.readline())T[i+1]=nodes[i].travel_cost# Khởi tạo mảng chi phí lưu thông LL=[[INFfor_inrange(n+1)]for_inrange(n+1)]# Khởi tạo mảng kết quảresults=[[INFfor_inrange(n+1)]for_inrange(n+1)]# Khởi tạo cho trường hợp một nút đi đến chính nóforiinrange(1,n+1):L[i][i]=0results[i][i]=T[i]# Đọc chi phí lưu thông l giữa hai nút i và kforuinrange(m):i,k,l=map(int,f.readline().split())L[i][k]=lL[k][i]=l# Tạm tính tổng chi phí ban đầu initial_total_cost=l+max(T[i],T[k])results[i][k]=initial_total_costresults[k][i]=initial_total_cost# Khởi tạo mảng các truy vấnqueries=[(0,0)]*r# Đọc các cặp nút cần truy vấnforiinrange(r):u_query,v_query=map(int,f.readline().split())queries[i]=(u_query,v_query)
Bước 0.3. Đối với C++, viết hàm so sánh để hỗ trợ cho hàm sort() sắp xếp các nút theo thứ tự chi phí hành trình T tăng dần.
Bước 1: Sắp xếp các nút theo chi phí hành trình tăng dần
Ta cần sắp xếp mảng nodes theo chi phí hành trình T tăng dần, vì khi duyệt các nút trung gian k (nút trung gian theo nghĩa của thuật toán Floyd-Warshall), ta luôn có được chi phí T là lớn nhất.
Nói cách khác, khi vòng lặp duyệt đến nút k (được lấy từ mảng nodes đã sắp xếp), thì T[k] là chi phí hành trình lớn nhất trong số các nút trung gian mà thuật toán đã xem xét tính đến thời điểm đó. Việc này nhằm bảo đảm thao tác cập nhật tổng chi phí results tại mỗi thời điểm là đúng đắn.
// nút trung gian k và phí hành trình t tại nút k intk,tk;// Duyệt từng nút theo thứ tự vừa sắp xếp ở trênfor(intp=0;p<n;++p){// Xét nút trung gian k và chi phí hành trình tại kk=nodes[p].id;tk=nodes[p].travel_cost;// Duyệt từng cặp nút u - vfor(intu=1;u<n+1;++u){for(intv=1;v<n+1;++v){// 1. Tính chi phí lưu thông khi đi qua nút trung gian kif(L[u][k]!=INF&&L[k][v]!=INF){L[u][v]=min(L[u][v],L[u][k]+L[k][v]);}// 2. Tính tổng chi phí kết quả tốt nhất (nếu có đường đi từ u đến v)if(L[u][v]!=INF){results[u][v]=min(results[u][v],L[u][v]+max({T[u],T[v],T[k]}));}}}// Bảo đảm tính đối xứng cho mảng results sau mỗi bước kfor(intu=1;u<n+1;++u){for(intv=u+1;v<n+1;++v){results[u][v]=min(results[u][v],results[v][u]);results[v][u]=results[u][v];}}}
# nút trung gian k và phí hành trình t tại nút k k=tk=0# Duyệt từng nút theo thứ tự vừa sắp xếp ở trênforpinrange(n):# Xét nút trung gian k và chi phí hành trình tại kk=nodes[p].idtk=nodes[p].travel_cost# Duyệt từng cặp nút u - vforuinrange(1,n+1):forvinrange(1,n+1):# 1. Tính chi phí lưu thông khi đi qua nút trung gian kifL[u][k]!=INFandL[k][v]!=INF:L[u][v]=min(L[u][v],L[u][k]+L[k][v])# 2. Tính tổng chi phí kết quả tốt nhất (nếu có đường đi từ u đến v)ifL[u][v]!=INF:results[u][v]=min(results[u][v],L[u][v]+max(T[u],T[v],T[k]))# Bảo đảm tính đối xứng cho mảng results sau mỗi bước kforuinrange(1,n+1):forvinrange(1,n+1):results[u][v]=min(results[u][v],results[v][u])results[v][u]=results[u][v]