11367 - Full Tank?

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11367 - Full Tank?

Post by andmej » 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] = 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

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

Re: 11367 - Full tank?

Post by andmej » 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.
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
Location: Dhaka,Bangladesh

Re: 11367 - Full tank?

Post by lnr » Fri Oct 10, 2008 12:13 pm

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

Post by Huitogi35 » 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

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

Re: 11367 - Full tank?

Post by lnr » Fri Nov 14, 2008 10:10 am

Is it related to this problem?

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

Re: 11367 - Full tank?

Post by andmej » 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.
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
Location: Dhaka,Bangladesh

Re: 11367 - Full tank?

Post by lnr » 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.........................................................................

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

Re: 11367 - Full tank?

Post by andmej » 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.
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?

Post by howardcheng » 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?

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

Re: 11367 - Full tank?

Post by howardcheng » 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.

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

Re: 11367 - Full tank?

Post by tanker5 » 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.

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

Re: 11367 - Full tank?

Post by lucastan » Mon Aug 29, 2011 7:34 am

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
Location: Bangladesh
Contact:

Re: 11367 - Full tank?

Post by Imti » 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 :)

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

Re: 11367 - Full Tank?

Post by novaten » 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.
Thanks in advance.

Post Reply

Return to “Volume 113 (11300-11399)”