## 11367 - Full Tank?

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### 11367 - Full Tank?

Hi, I tried the problem using Dijkstra's algorithm but I get Time Limit Exceeded.

My state is <i, g> which means I can reach node i having g units of fuel in my tank. I do a STL priority_queue search.

Is there a possible optimization or must I change my approach (DP maybe)?

Thanks a lot for the help.

Here's my code, just in case:

Code: Select all

``````/*
Time limit exceeded!
*/
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

const int MAXN = 1000, MAXC = 100;

struct edge{
int i, g, w;
edge(){}
edge(int I, int G, int W) : i(I), g(G), w(W) {}
bool operator < (const edge &that) const {
return w > that.w;
}
};

int p[MAXN], d[MAXN][MAXC+1], n;
vector<edge> g[MAXN];

int dijkstra(const int &start, const int &end, const int &c){
for (int i=0; i<n; ++i)
for (int j=0; j<=c; ++j)
d[i][j] = INT_MAX;

priority_queue<edge> q;
q.push(edge(start, 0, 0));
d[start][0] = 0;

while (q.size()){
edge u = q.top();
q.pop();

//printf("popped <%d, %d, %d>\n", u.i, u.g, u.w);
if (u.i == end){
return u.w;
}
if (d[u.i][u.g] < u.w) continue;

vector<edge> &v = g[u.i];
for (int j=0; j<v.size(); ++j){
int distance = v[j].w;
int neighbor = v[j].i;
for (int k = distance - u.g; k <= c + distance - u.g; ++k){
int new_gas = u.g - distance + k;
if (k >= 0 && 0 <= new_gas && u.g + k <= c ){
int w_extra = k*p[u.i];
assert(w_extra >= 0);
if (u.w + w_extra < d[neighbor][new_gas]){
d[neighbor][new_gas] = u.w + w_extra;
q.push(edge(neighbor, new_gas, u.w + w_extra));
//printf("  pushed <%d, %d, %d>\n", neighbor, new_gas, u.w + w_extra);
}
}
}
}
}
return INT_MAX;

}

int main(){
int m;
scanf("%d %d", &n, &m);
for (int i=0; i<n; ++i){
scanf("%d", &p[i]);
}

while (m--){
int u, v, d;
scanf("%d %d %d", &u, &v, &d);
g[u].push_back(edge(v, 0, d));
g[v].push_back(edge(u, 0, d));
}

int q;
scanf("%d", &q);
while (q--){
int c, s, e;
scanf("%d %d %d", &c, &s, &e);
int t = dijkstra(s, e, c);
if (t < INT_MAX){
printf("%d\n", t);
}else{
printf("impossible\n");
}
}
return 0;
}
``````
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11367 - Full tank?

OK, I've optimized and got accepted. Just in case anyone cares, the observation is that if you are in state <i, g> you have two choices:

-> For every neighbor j of i you can go to state <j, g - distance(i, j)> spending no extra money and only if g - distance(i, j) > 0, that is, if you have enough fuel to advance.
-> Or you can stay right where you are buying a gallon of gas, going to state <i, g+1> spending price_at(i) dollars.

In my previous code, I made the same search but pushing a lot more states into the priority queue, which makes it much slower.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 11367 - Full tank?

Would someone give hint ?
Last edited by lnr on Fri Nov 14, 2008 10:11 am, edited 2 times in total.

Huitogi35
New poster
Posts: 1
Joined: Tue Oct 28, 2008 3:22 am
Contact:

### hi

just my two cents
bump

cheap wow power leveling (World of warcraft Power Leveling):
buy WoW Power Leveling, cheap world of warcraft power leveling , 1-80 level wow Power Leveling,maple story mesos, wedding invitations

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 11367 - Full tank?

Is it related to this problem?

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11367 - Full tank?

I solved it using Dijkstra's algorithm. But your state must contain the amount of fuel that you currently have in the tank.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 11367 - Full tank?

andmej wrote:
But your state must contain the amount of fuel that you currently have in the tank.
Would you please explain it with calculation in detail?
pls.........................................................................

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11367 - Full tank?

Imagine you build a graph where each node is a pair of integers; let's call them where and fuel. So, if we reach a node <where, fuel> in this new graph, it means that we can reach node "where" from the original graph in such a way that we have exactly "fuel" units of fuel in our tank at the moment we reach node "where".

We will add edges between these nodes; the weight of these edges will represent the money spent from a node to an another.

The answer to the problem would then be the shortest path from node <start_node, 0> (0 because we start with an empty tank) to a node in the form of <end_node, any_fuel> (We don't really care of how much fuel we have at the end, as long as the total cost is as cheap as possible).

Now, to build the edges of this new graph we have 2 options.
From state <where, fuel> there will be a edge to the following new nodes:
* <neighbour, fuel - distance[where][neighbour] >. In this case, "neighbour" is adjacent to "where" in the original graph. This edge represents the idea of moving between cities and burning fuel. You move to a new city, but your fuel decreases by the same amount of miles that you drove. The weight of this kind of edges will be 0, because you didn't spend any money. Notice that this edge can only be used if "fuel" is enough to reach the new city.

*<where, fuel + 1>. In this case, we stay right where we are but we buy an extra gallon of gas. Now, the weight of this kind of edges will be price_at[where], because we buy a gallon. Notice that this edge can only be used if we still have some free capacity in the tank.

Hope that helps.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

### Re: 11367 - Full tank?

I build exactly the graph that you say and run my own Dijkstra algorithm for each query, but it always runs too long. Is there some way to optimize it so that Dijkstra only has to be run once?

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

### Re: 11367 - Full tank?

howardcheng wrote:I build exactly the graph that you say and run my own Dijkstra algorithm for each query, but it always runs too long. Is there some way to optimize it so that Dijkstra only has to be run once?
Never mind. I got under the time limit by using vectors instead of list in STL.

tanker5
New poster
Posts: 1
Joined: Thu Aug 04, 2011 8:18 pm

### Re: 11367 - Full tank?

I had the same problem with speed. Tried List at first, but vectors seem to be more efficient.

lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

### Re: 11367 - Full tank?

anyone can explain why the sample output for the first case is 170 ?

Thanks!

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11367 - Full tank?

Well,Here's how 170 comes
1)Fill tank with 9 unit from city 0 and go to city 1 which costs 9 unit of fuel(9*10=90)
2)From station 1 take 8 unit of fuel and go to station 2 which costs 1 unit of fuel(8*10=70)
3)Go from station 2 to destination 3 which needs 7 unit of of fuel .so here u don't need any more fuel
so cost is 170.
Hope u got it

novaten
New poster
Posts: 2
Joined: Wed Dec 23, 2015 7:38 am

### Re: 11367 - Full Tank?

Hi,

I can not get clearly a thing , how do you know, base on the description that the graph is both ways? . I have uploaded my code several times and always getting WA, I started to realize that i just added one direction edges.