ACM/ICPC Indonesia National Contest 2007 - Qualification
Problem E
Taxi!
Time Limit: 1s| Taxi Driver | : "Where to go, sir?" |
| Passenger | : "Kemanggisan, Binus Campus, please." |
| Taxi Driver | : "Okay, and which way to go?" |
| Passenger | : "Just take the fastest one." |
This kind of conversation usually happens when we take a taxi. Many people think that the fastest way would mean the cheapest one as well. But it's not always true! Sometimes the fastest way could be more expensive than the slower one and vice versa, some factors are: toll fee, longer road without traffic jam, etc.
We will model this kind of situation on this problem. The city has n intersections and m bidirectional roads connecting pairs of intersections. Each road will cost you a certain time and money (taxi fare). Write a program to find the minimum time to take you to your destination however the travel expenses must not exceed your money.
Input Specification
The first line of each case contains two integers, n (1 <= n <= 100) intersections and m roads. The intersections are numbered from 0 to n-1. The next m lines will each contains four integers: u, v, t, and c (1 <= t,c <= 100), means that there is a road from intersection u to intersection v and vice versa which will cost you t minute(s) and c Rupiah(s). The last line of each case will contains three integers: s, d, and r (1 <= r <= 100), means that you want to go to d (your destination point) from s (your starting point) while you only have r Rupiah(s).Output Specification
For each case, output in a single line the minimum time to reach your destination while the total cost doesn't exceed your money.Sample Input
3 3 0 2 16 19 0 1 9 12 1 2 5 13 0 2 20 4 5 0 1 2 11 1 2 7 27 2 3 4 10 0 3 6 25 3 1 5 12 0 2 35
Sample Output
16 10
Problem Setter: Suhendry Effendy
Pembahasan Problem E - Taxi!
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();
}
}
No comments:
Post a Comment