## 11367 - Full tank?

Moderator: Board moderators

### 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

andmej
Experienced poster

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

### 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.

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm

### hi

just my two cents
bump

cheap wow power leveling (World of warcraft Power Leveling):
Huitogi35
New poster

Posts: 1
Joined: Tue Oct 28, 2008 3:22 am

### Re: 11367 - Full tank?

Is it related to this problem?

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm

### 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

andmej
Experienced poster

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

### 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.........................................................................

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm

### 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

andmej
Experienced poster

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

### 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: 68
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.
howardcheng
Learning poster

Posts: 68
Joined: Thu Aug 21, 2003 1:56 am

### Re: 11367 - Full tank?

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

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

### Re: 11367 - Full tank?

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

Thanks!
lucastan
New poster

Posts: 9
Joined: Sat Jul 02, 2011 6:46 am

### 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
Imti
Learning poster

Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm