Felix Halim .NET  
Google 
Name:  Message:

Problem E - Taxi!

Complete Problem Statement here

Diberikan N persimpangan dan M jalan yang menghubungkannya. Anda ingin berpergian dari persimpangan A ke persimpangan B, tetapi anda hanya mempunyai uang sebanyak R rupiah. Setiap M jalan yang menghubungkan 2 persimpangan, tercatat harga dan waktu untuk melewati jalan tersebut (arahnya tidak masalah). Anda tidak peduli uang anda habis terpakai semua atau tersisa (tetapi tidak boleh negative!), anda hanya peduli waktu tercepat yang mungkin dari A ke B menggunakan uang R rupiah. Berapakah waktu tercepat tersebut?

Ini adalah soal tersulit di babak penyisihan. Karena untuk menyelesaikannya, anda setidaknya harus bisa rekursi + memo (dp topdown) atau A* complete search. Dijkstra yang hanya berdasarkan waktu tidak mempan disini karena ada kasus dimana waktu tercepat membutuhkan uang melebihi R rupiah, jadi anda harus memilih waktu ke-2 atau ke-3 tercepat, dst.. sampai waktu ke-x tercepat dimana hanya membutuhkan uang kurang atau sama dengan R rupiah.

Dynamic Programming dengan topdown approach (rekursi + memo) merupakan cara paling gampang untuk menyelesaikan problem ini. State dari Dynamic Programmingnya adalah fastest[P][U], artinya: berapa waktu tercepat untuk sampai ke tujuan dari posisi P, dengan sisa uang U. Jika anda bisa mengisi semua tabel ini, maka jawabannya adalah fastest[A][R]. Cara mengisi tabel tersebut, bisa menggunakan rekursi. Untuk lebih jelasnya, lihat source code taxi-dp-topdown.c dibawah.

A* adalah suatu cara pencarian yang komplit (complete search), artinya semua possibility akan dipertimbangkan. Kelemahannya adalah state space nya akan meluas dengan cepat (boros memory) dan agak lambat sedikit (ada faktor log(n) dari priority queue sewaktu insert ataupun extractMin). Tetapi A* akan sangat cepat jika solusinya selalu ada dan heuristic yang dipakai bagus.

Untuk problem ini, A* nya bisa dilakukan dengan meng-generate semua possible paths, dan menjalankan terlebih dahulu jalan yang paling murah. Untungnya, di problem ini A* nya bisa dibantu dengan sedikit "memo" sehingga bisa berjalan cepat. Memo nya adalah jangan memproses lagi path yang melalui suatu persimpangan yang time nya lebih besar dari sebelumnya. A* ini akan berjalan sekitar O(N^2). Memo ini akan berhasil karena jika ada path lain yang mengunjungi node yang sudah pernah dikunjungi, berarti costnya sekarang lebih mahal (karena A* selalu memproses yang costnya murah dahulu). Kalau cost sekarang lebih mahal, kita tinggal lihat apakah waktu sekarang lebih cepat? kalau tidak lebih cepat, maka tidak perlu lagi dilanjutkan (akan selalu rugi).

Yang membuat soal ini agak susah adalah, anda harus membuat Priority Queue data structure sendiri untuk mengimplementasinya jika tidak mau maka anda harus menguasai STL priority_queue di C++. Soal ini bukan soal mudah :) Saya sertakan kode A* dengan Priority Queue bikinan sendiri (yang lebih lambat, versi O(N)) dan kode A* dengan STL priority_queue (yang lebih cepat, O(log(N))).

Solusi Java untuk A* mungkin lebih mudah dimengerti daripada versi C/C++ karena Java 5 juga support Priority Queue

Note: A* diatas tidak ada heuristic functionnya, jadi bisa dibilang A* degenerate menjadi Dijkstra biasa.

#include <stdio.h>
#include <string.h>

int n,A,B,inf=1000000000;
int waktu[100][100];
int harga[100][100];
int memo[100][101];

int fastest(int P, int R){
    int i, ret = inf;
    if (P==B) return 0;
    if (memo[P][R]!=-1) return memo[P][R];

    for (i=0; i<n; i++){
        if (waktu[P][i]!=-1 && R>=harga[P][i]){
            int t = waktu[P][i] + fastest(i,R-harga[P][i]);
            if (t < ret) ret = t;
        }
    }
    return memo[P][R] = ret;
}

int main(){
    int m,u,v,t,c,i,R;
    
    while (scanf("%d %d",&n,&m)!=EOF){
        memset(waktu,-1,sizeof(waktu));
        memset(harga,-1,sizeof(harga));
        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&A,&B,&R);
        memset(memo,-1,sizeof(memo));
        printf("%d\n",fastest(A,R));
    }
}
#include <stdio.h>
#include <stdlib.h>

#define MAXN 105
#define INF 1000000

typedef struct {
    int harga, waktu, pos;
} Node;

int nodecmp(const void *a, const void *b){
    Node *na = (Node*) a;
    Node *nb = (Node*) b;
    return na->harga - nb->harga;
}

Node pq[100000];
int harga[MAXN][MAXN];
int waktu[MAXN][MAXN];
int bestTime[MAXN];

int main(){
    int n,m,u,v,t,c,duit,i,pqSize;

    while (scanf("%d %d",&n,&m)!=EOF){
        for (u=0; u<n; u++){
            for (v=0; v<n; v++) waktu[u][v] = -1;
            bestTime[u] = INF;
        }

        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&u,&v,&duit);

        pq[0] = (Node){0,0,u};
        pqSize = 1;
        while (pqSize > 0){
            qsort(pq,pqSize,sizeof(Node),nodecmp); // sort berdasarkan harga termurah
            Node node = pq[0];
            pq[0] = pq[--pqSize]; // timpa elemen pertama dengan terakhir

            if (bestTime[node.pos] <= node.waktu) continue;
            bestTime[node.pos] = node.waktu;
            if (node.pos == v) continue;

            for (i=0; i<n; i++) {
                if (waktu[node.pos][i]==-1) continue;
                if (node.harga + harga[node.pos][i] > duit) continue;
                pq[pqSize++] = (Node){
                    node.harga + harga[node.pos][i],
                    node.waktu + waktu[node.pos][i],
                    i
                };
            }
        }
        
        printf("%d\n",bestTime[v]);
    }
}
#include <stdio.h>
#include <queue>

using namespace std;

#define MAXN 105
#define INF 1000000

typedef struct Node {
    int harga, waktu, pos;

    bool operator<(Node const &that) const {
        return harga > that.harga;
    }
} Node;

int harga[MAXN][MAXN];
int waktu[MAXN][MAXN];
int bestTime[MAXN];

int main(){
    int n,m,u,v,t,c,duit,i;

    while (scanf("%d %d",&n,&m)!=EOF){
        for (u=0; u<n; u++){
            for (v=0; v<n; v++) waktu[u][v] = -1;
            bestTime[u] = INF;
        }

        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&u,&v,&duit);

        priority_queue<Node> pq;
        pq.push((Node){0,0,u});
        while (!pq.empty()){
            Node node = pq.top(); pq.pop();

            if (bestTime[node.pos] <= node.waktu) continue;
            bestTime[node.pos] = node.waktu;
            if (node.pos == v) continue;

            for (i=0; i<n; i++) {
                if (waktu[node.pos][i]==-1) continue;
                if (node.harga + harga[node.pos][i] > duit) continue;
                pq.push((Node){
                    node.harga + harga[node.pos][i],
                    node.waktu + waktu[node.pos][i],
                    i
                });
            }
        }
        
        printf("%d\n",bestTime[v]);
    }
}
import java.util.*;

public class TaxiAStar {
    class Node implements Comparable<Node> {
        int harga, waktu, pos;

        public Node(int harga, int waktu, int pos){
            this.harga = harga;
            this.waktu = waktu;
            this.pos = pos;
        }

        public int compareTo(Node that){
            return this.harga - that.harga;
        }
    }

    int[][] harga;
    int[][] waktu;
    int[] bestTime;

    public void solve(){
        Scanner scan = new Scanner(System.in);

        while (scan.hasNextInt()){
            int N = scan.nextInt();
            int M = scan.nextInt();

            harga = new int[N][N];
            waktu = new int[N][N];
            bestTime = new int[N];

            for (int i=0; i<N; i++){
                for (int j=0; j<N; j++)
                    waktu[i][j] = -1;
                bestTime[i] = 1000000000;
            }

            for (int i=0; i<M; i++){
                int u = scan.nextInt();
                int v = scan.nextInt();
                int t = scan.nextInt();
                int c = scan.nextInt();
                waktu[u][v] = waktu[v][u] = t;
                harga[u][v] = harga[v][u] = c;
            }

            int A = scan.nextInt();
            int B = scan.nextInt();
            int R = scan.nextInt();

            PriorityQueue<Node> pq = new PriorityQueue<Node>();
            pq.offer(new Node(0,0,A));
            while (pq.size()>0){
                Node node = pq.poll();

                if (bestTime[node.pos] <= node.waktu) continue;
                bestTime[node.pos] = node.waktu;
                if (node.pos == B) continue;

                for (int i=0; i<N; i++){
                    if (waktu[node.pos][i]==-1) continue;
                    if (node.harga + harga[node.pos][i] > R) continue;
                    pq.offer(new Node(
                        node.harga + harga[node.pos][i],
                        node.waktu + waktu[node.pos][i],
                        i
                    ));
                }
            }
            
            System.out.printf("%d\n",bestTime[B]);
        }

        scan.close();
    }

    public static void main(String[] args){
        new TaxiAStar().solve();
    }
}

Lihat problem lain:

  1. The Chosen Sub Matrix
  2. Avoiding Financial Nightmare
  3. No Pause Telegraph
  4. Burger, French Fries, Soft Drink
  5. Taxi!
Kembali ke halaman utama

© Felix Halim 2009 (Loaded in 0.00209 secs)