Page 1 of 1

### 11367 - Full Tank?

Posted: Sun Jul 13, 2008 5:08 am
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;

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;
}
``````

### Re: 11367 - Full tank?

Posted: Sun Jul 20, 2008 4:40 am
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.

### Re: 11367 - Full tank?

Posted: Fri Oct 10, 2008 12:13 pm
Would someone give hint ?

### hi

Posted: Fri Oct 31, 2008 9:48 pm
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

### Re: 11367 - Full tank?

Posted: Fri Nov 14, 2008 10:10 am
Is it related to this problem?

### Re: 11367 - Full tank?

Posted: Tue Nov 18, 2008 5:51 am
I solved it using Dijkstra's algorithm. But your state must contain the amount of fuel that you currently have in the tank.

### Re: 11367 - Full tank?

Posted: Tue Nov 18, 2008 1:44 pm
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.........................................................................

### Re: 11367 - Full tank?

Posted: Tue Nov 18, 2008 4:59 pm
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.

### Re: 11367 - Full tank?

Posted: Fri Jun 17, 2011 8:22 pm
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?

### Re: 11367 - Full tank?

Posted: Fri Jun 17, 2011 8:24 pm
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.

### Re: 11367 - Full tank?

Posted: Thu Aug 04, 2011 8:29 pm
I had the same problem with speed. Tried List at first, but vectors seem to be more efficient.

### Re: 11367 - Full tank?

Posted: Mon Aug 29, 2011 7:34 am
anyone can explain why the sample output for the first case is 170 ?

Thanks!

### Re: 11367 - Full tank?

Posted: Mon Nov 28, 2011 9:18 pm
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 ### Re: 11367 - Full Tank?

Posted: Wed Dec 23, 2015 7:44 am
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.