ACM/ICPC Indonesia National Contest 2007
Problem F
Jakarta Traffic Jam
Time Limit: 1sThe traffic in Jakarta is terrible. Streets in Jakarta may get congested with traffic jam during rush hour. This means it will take longer time to pass through those streets since you can only drive half your speed during rush hours. Therefore, you need to plan your trip carefully if you don't want to be late for your activities.
For example, consider a street from P to Q which will need 20 minutes to drive in a normal time. The street is congested with traffic at 15:00 until 16:00. Now, let's consider some sample conditions that might happen related to rush hours:
- If you start your trip 15 minutes before the rush hour (start from P at 14:45), then when the traffic starts to get congested, you can only drive half of your normal speed, thus, you will need 10 (2x5) more minutes to reach Q. Thus, the total time you need to go from P to Q is 15 + 10 = 25 minutes.
- If you start your journey at the last 5 minutes of the rush hour (start from P at 15:55), the distance you have reached in the first 5 minutes is equal to the distance you can reach in 2.5 minutes during normal hours. You will need 17.5 more minutes to get to Q. Thus, the total time you need to go from P to Q is 5 + 17.5 = 22.5 minutes.
- Other combinations of (a) and (b).
Input
The input contains several test cases. Each case begins with two integers N (1<= N <=20) and M. Each intersection will be numbered from 0 to N-1.The first three integers P, Q, and T (1<= T <=50) in each of the following M line means there is a street connecting intersection P to intersection Q which need T minutes driving in normal time. These integers will be followed by either character 'N' or 'R'. 'N' will not be followed by any characters and it means the street has no rush hours. 'R' will be followed by the starting and ending time of the rush hour in the format of hh:mm (00:00 to 23:59). No rush hours will rollover past midnight.
The last line of each case contains s - your starting point, d - your destination and w - current time.
Input is terminated by a line containing two zeroes. This line should not be processed.
Output
For each case, output a line containing the minimum time you need to go from s to d in minutes. Your output should always contain two digits after the decimal point.Sample Input
2 1 0 1 20 R 15:00 16:00 0 1 14:45 3 3 0 1 20 R 15:00 16:00 1 3 10 N 2 1 35 R 16:30 17:00 0 2 15:55 0 0
Sample Output
25.00 72.50
Problem Setter: Danny Gunawan
Pembahasan Problem F - Jakarta Traffic Jam
Soal ini secara algoritma lebih mudah daripada soal Taxi di babak penyisihan, tetapi bobotnya dipindahkan ke matematika!
Ada N persimpangan dan M jalan. Setiap jalan mempunyai jam kemacetan dimana kalau anda melalui jalan tersebut saat macet maka kecepatan anda akan menurun setengah kecepatan awal. Pertanyaannya, berapakah waktu tercepat dari s ke d?
Anda tidak perlu A* seperti soal Taxi di penyisihan, algoritma umum Dijkstra bisa diterapkan untuk memecahkan soal ini karena anda hanya perlu meminimalisasi waktu dari source ke destination. Tepat seperti apa yang Dijkstra lakukan. Bagaimanapun juga, A* adalah versi superior dan kode nya pun tidak jauh beda dengan Dijkstra dan mungkin lebih gampang di implementasi. Untuk belajar A*, anda bisa buka pembahasan soal penyisihan Taxi. Untuk belajar Dijkstra anda bisa lihat pembahasan soal ini.
Saya akan coba menjelaskan Dijkstra secara kasarnya saja. Untuk cara formalnya, anda bisa baca dari buku Introduction to Algorithms atau cari sendiri lewat Google :)
Cara Dijkstra bekerja adalah dengan selalu memprocess node yang memiliki waktu tercepat dan berhenti saat semua node sudah diprocess. Dalam memprocess suatu node, node tersebut akan meng-update waktu yang dibutuhkan untuk tiba di node lain dari node tersebut. Saat suatu node diprocess, maka waktu tercepat untuk sampai ke node tersebut sudah diketahui dengan pasti. Silahkan lihat dibawah untuk implementasinya.
#include <stdio.h>
// ini adalah function mematikan dari soal ini, membutuhkan sedikit if dan else + rekursi :)
double calculate(double waktuSekarang, double lamaPerjalanan, int rushStart, int rushEnd){
double waktuTiba = waktuSekarang + lamaPerjalanan;
if (rushStart <= waktuSekarang && waktuSekarang <= rushEnd){
// waktu mulainya kena rush hour, case yang B
// berapa lama lagi sampai rush hournya berhenti
double lamanyaRushHour = rushEnd - waktuSekarang;
if (lamanyaRushHour > lamaPerjalanan * 2){
// sepanjang anda berjalan, macet melulu
return lamaPerjalanan * 2;
} else {
// ditengah-tengah perjalanan anda berhasil lolos dari rush hour
double jarakTersisa = lamaPerjalanan - lamanyaRushHour/2;
return lamanyaRushHour + jarakTersisa;
}
} else if (waktuSekarang <= rushStart && rushStart <= waktuTiba){
// ditengah perjalanan anda terkena rush hour, case yang A
// anda bisa jalan dengan kecepatan normal saat belum terkena rush hour
double jalanNormal = rushStart - waktuSekarang;
// disinilah anda mulai terkena rush hour dan kalau dilihat, anda mirip Case B diatas
// yaitu anda memulai dengan terkena rush hour! maka tinggal panggil aja calculate() sekali lagi ;)
return jalanNormal + calculate(
waktuSekarang + jalanNormal, // waktu sekarang sudah bertambah sebanyak perjalanan yang ditempuh
lamaPerjalanan - jalanNormal, // lama perjalanan berkurang sebanyak yang ditempuh
rushStart, rushEnd); // waktu rush hour start dan end masih tetap sama
} else {
return lamaPerjalanan; // anda mujur sekali tidak terkena rush hour
}
}
int getTime(){
int hh,mm;
scanf("%d:%d",&hh,&mm);
return hh*60 + mm;
}
int main(){
int travel_time[20][20]; // travel_time[i][j] waktu normal berjalan dari i ke j
int rush_start[20][20]; // rush_start[i][j] waktu mulai rush hour untuk jalan i ke j
int rush_end[20][20]; // rush_end[i][j] waktu selesai rush hour untuk jalan i ke j
double waktu[20]; // waktu[x] adalah waktu tercepat untuk sampai di node x
int N,M,i,j,k,P,Q,T,s,d,pq[20],pqSize;
char NR[2];
while (scanf("%d %d",&N,&M)!=EOF && (N||M)){
memset(travel_time,-1,sizeof(travel_time));
memset(rush_start,-1,sizeof(rush_start));
memset(rush_end,-1,sizeof(rush_end));
for (i=0; i<M; i++){
scanf("%d %d %d %s",&P,&Q,&T,NR);
travel_time[P][Q] = travel_time[Q][P] = T;
if (NR[0]=='R'){
rush_start[P][Q] = rush_start[Q][P] = getTime();
rush_end[P][Q] = rush_end[Q][P] = getTime();
}
}
scanf("%d %d",&s,&d);
for (i=0; i<N; i++){
pq[i] = i; // masukkan semua node ke Priority Queue
waktu[i] = 1e10; // waktu di semua node adalah tak terhingga
}
waktu[s] = getTime(); // set waktu dari starting intersection s
// Dijkstra, process berdasarkan waktu yang paling pagi
for (pqSize=N; pqSize>0; pqSize--){
// cari node terpagi yang belum diprocess
k = 0;
for (i=1; i<pqSize; i++)
if (waktu[pq[i]] < waktu[pq[k]])
k = i; // update k kalau ketemu node yang lebih pagi
i = pq[k]; // pq[k] adalah node dengan waktu terpagi, simpan di i
pq[k] = pq[pqSize-1]; // buang node k dari priority queue
// process node i (node yang terpagi saat ini)
for (j=0; j<N; j++){
if (travel_time[i][j]!=-1){
double duration = travel_time[i][j];
if (rush_start[i][j]!=-1){
duration = calculate( // hitung durasi waktu yang diperlukan dari intersection i ke j
waktu[i], // waktu saat ini
travel_time[i][j], // waktu perjalanan normal dari i ke j
rush_start[i][j], // jam mulai rush hour untuk jalan i ke j
rush_end[i][j]); // jam selesai rush hour untuk jalan i ke j
}
// jika kita bisa travel ke j dari i lebih cepat, maka update waktu j
if (waktu[i] + duration < waktu[j]){
waktu[j] = waktu[i] + duration;
}
}
}
}
// waktu tercepat sampai di destination d adalah waktu di d dikurang dengan waktu di s
printf("%.2lf\n", waktu[d] - waktu[s]);
}
}
No comments:
Post a Comment