Felix Halim .NET  
Google 
Name:  Message:

Problem F - Jakarta Traffic Jam

Complete Problem Statement here

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]);
    }
}

Lihat problem lain:

  1. Minimum Swap
  2. GCD!
  3. Playing With Domino
  4. Email from the Professor
  5. Panda Number
  6. Jakarta Traffic Jam
  7. Sultan's Land
  8. Tree Median
Kembali ke halaman utama

© Felix Halim 2009 (Loaded in 0.00184 secs)