padma_nadir_majhi's blog

need some hints :lightoj 1254
By padma_nadir_majhi, history, 7 years ago, In English

http://www.lightoj.com/volume_showproblem.php?problem=1254 how can i solve this problem?please need some help;

Michael Scofield has just broken out of the prison. Now he wants to go to a certain city for his next unfinished job. As you are the only programmer on his gang, he asked your help. As you know that the fuel prices vary in the cities, you have to write a code to help Scofield that instructs him where to take the fuel and which path to choose. Assume that his car uses one unit of fuel in one unit of distance. Now he gives you the starting city s where he starts his journey with his car, the destination city t and the capacity of the fuel tank of his car c, the code should find the route that uses the cheapest fuel cost. You can assume that Scofield's car starts with an empty fuel tank.

Input Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (2 ≤ n ≤ 100) and m (0 ≤ m ≤ 1000) where n denotes the number of cities and m denotes the number of roads. The next line contains n space separated integers, each lies between 1 and 100. The ith integer in this line denotes the fuel price (per unit) in the ith city. Each of the next m lines contains three integers u v w (0 ≤ u, v < n, 1 ≤ w ≤ 100, u ≠ v) denoting that there is a road between city u and v whose length is w.

The next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries by Scofield. Each of the next q lines contains the request. Each request contains three integers: c s t (1 ≤ c ≤ 100, 0 ≤ s, t < n) where c denotes the capacity of the tank, s denotes the starting city and t denotes the destination city.

Output For each case, print the case number first. Then for each query print the cheapest trip from s to t using the car with the given capacity c or 'impossible' if there is no way of getting from s to t with the given car.

Sample Input Output for Sample Input 1

5 5

10 10 20 12 13

0 1 9

0 2 8

1 2 1

1 3 11

2 3 7

2

10 0 3

20 1 4

Case 1:

170

impossible

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by padma_nadir_majhi (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This problem is equal UVA 11367, but have multiple test cases. One way to solve is run dijkstra, but store two states (location, fuel). So let's consider you are in location u, and your current fuel is d, foreach location v adjacent to u if the cost to travel from u to v is x and x <= d you can travel to v with fuel equal d — x. Now other option is stay in city u and take more one unit of fuel if d + 1 <= c with cost p[u].

In icpc3 book, have a explained solution for this exercise in page 150.

My code from UVA 11367 goes bellow.

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, INF = (int) 1e9;
typedef pair<int, int>	pii;
typedef pair<int, pii> pipii;
priority_queue<pipii>pq;
vector<pii>adj[N];
int dis[N][N];
int n, m;
int p[N];

int dijkstra(int s, int e, int c){
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j <= c ; j++){
			dis[i][j] = INF;
		}
	}
	
	dis[s][0] = 0;
	
	pq.push(make_pair(0 , make_pair(0, s)));
	
	while(!pq.empty()){
		int u = pq.top().second.second;
		int cur = pq.top().second.first;
		//cout << u << ' ' << cur << '\n';
		pq.pop();
		
		for(int k = 0 ; k < adj[u].size() ; k++){
			int v = adj[u][k].first;
			int x = adj[u][k].second;
			
			if(cur >= x){
			
				if(dis[v][cur - x] > dis[u][cur]){
					dis[v][cur - x] = dis[u][cur];
					pq.push(make_pair(-dis[v][cur - x], make_pair(cur - x, v)));
				}
				
			}
		}
		
		if(cur + 1 <= c){
			if(dis[u][cur + 1] > dis[u][cur] + p[u]){
				dis[u][cur + 1] = dis[u][cur] + p[u];
				pq.push(make_pair(-dis[u][cur + 1], make_pair(cur + 1, u)));
			}
		}
	}
		
	return dis[e][0];
}

int main (){
	scanf("%d%d", &n, &m);
	
	for(int i = 0 ; i < n ; i++){
		scanf("%d", &p[i]);
	}
	
	for(int i = 0 ; i < m ; i++){
		int u, v, w;
		
		scanf("%d%d%d", &u, &v, &w);
		
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}
	
	int q;
	
	scanf("%d", &q);
	
	while(q--){
		int c, s, e;
		scanf("%d%d%d", &c, &s, &e);
		
		int d = dijkstra(s, e, c);
		
		if(d == INF){
			printf("impossible\n");
		}else{
			printf("%d\n", d);
		}
	}
	
	return 0;
}
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please don't copy the whole problem statement. That is a copyright infringement. Please only leave a link; that is enough.

→ Reply