12661 - Funny Car Racing

All about problems in Volume 126. 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
Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

12661 - Funny Car Racing

Post by Farsan » Sat May 24, 2014 5:30 am

WA... critical I/O?

Code: Select all

AC
Last edited by Farsan on Sat Jun 28, 2014 6:33 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12661 Funny Car Racing

Post by brianfry713 » Thu Jun 12, 2014 12:28 am

Change line 100 to:
m = st1.tm % (x + y);
Check input and AC output for thousands of problems on uDebug!

Ra1nWarden
New poster
Posts: 2
Joined: Sun Sep 15, 2013 3:49 am

Re: 12661 - Funny Car Racing

Post by Ra1nWarden » Mon May 18, 2015 10:12 am

I am not sure what is wrong with this. Please take a look. Keep getting WA. Thanks!

Code: Select all

#include <cstdio>
#include <queue>
#include <cstring>
#define MAXN 305
#define INF 1000000000

using namespace std;

struct Edge {
  int u, v, a, b, t;
  Edge(int uu, int vv, int aa, int bb, int tt) : u(uu), v(vv), a(aa), b(bb), t(tt) {}
};

int n, m, s, t;
bool visited[MAXN];
vector<int> graph[MAXN];
vector<Edge> edges;
int d[MAXN];

typedef pair<int, int> HeapNode;

int main() {
  int kase = 1;
  while(scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
    for(int i = 1; i <= n; i++)
      graph[i].clear();
    edges.clear();
    for(int i = 0; i < m; i++) {
      int u, v, a, b, time;
      scanf("%d %d %d %d %d", &u, &v, &a, &b, &time);
      edges.push_back(Edge(u, v, a, b, time));
      edges.push_back(Edge(v, u, a, b, time));
      graph[u].push_back(edges.size() - 2);
      graph[v].push_back(edges.size() - 1);
    }
    memset(visited, false, sizeof visited);
    for(int i = 1; i <= n; i++)
      d[i] = INF;
    d[s] = 0;
    priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode> > pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()) {
      HeapNode next = pq.top();
      pq.pop();
      int u = next.second;
      int cst = next.first;
      if(visited[u])
	continue;
      visited[u] = true;
      for(int i = 0; i < graph[u].size(); i++) {
	Edge& e = edges[graph[u][i]];
	if(e.t <= e.a) {
	  int left = cst % (e.a + e.b);
	  int cost = INF;
	  if(e.a - left >= e.t) {
	    cost = e.t;
	  } else {
	    cost = e.a + e.b - left + e.t;
	  }
	  if(d[e.v] > cost + d[u]) {
	    d[e.v] = cost + d[u];
	    pq.push(make_pair(cost + d[u], e.v));
	  }
	}
      }
    }
    printf("Case %d: %d\n", kase++, d[t]);
  }
  return 0;
    
}

Post Reply

Return to “Volume 126 (12600-12699)”