## 12047 - Highest Paid Toll

Moderator: Board moderators

phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

### 12047 : Highest Paid Toll getting TLE in java

I am getting TLE in this problem. I have first taken out the shortest path to each vertex in the original graph(g) from s, and then the shortest path to each vertex in reversed graph(rg) from t. Then for each edge(u,v,c), if shortest path in g to u + shortest path in rg to v + c <=p, then i am updating max with c. The algo looks correct. How can I better the execution time ? Here is my code :

Code: Select all

``````public class HighestPaidToll_12047 {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int test = in.nextInt();
int n, m, s, t, p, i, a, b, c;
List<Edge> graph[] = new List[10000];
List<Edge> rGraph[] = new List[10000];
Vertex vertex[] = new Vertex[10000];
Vertex rVertex[] = new Vertex[10000];
Edges edges[] = new Edges[100000];
for(i=0;i<10000;i++) {
graph[i] = new ArrayList<Edge>(1000);
rGraph[i] = new ArrayList<Edge>(1000);
vertex[i] = new Vertex(i);
rVertex[i] = new Vertex(i);
}
while (test-- > 0) {
n = in.nextInt();
m = in.nextInt();
s = in.nextInt() - 1;
t = in.nextInt() - 1;
p = in.nextInt();
for(i=0;i<n;i++) {
graph[i].clear();
rGraph[i].clear();
vertex[i].key = Integer.MAX_VALUE;
rVertex[i].key = Integer.MAX_VALUE;
vertex[i].visited = false;
rVertex[i].visited = false;
}

for(i=0;i<m;i++) {
a = in.nextInt() - 1;
b = in.nextInt() - 1;
c = in.nextInt();
edges[i] = new Edges(a, b, c);

}
Dijkstra(graph, vertex, s);
Dijkstra(rGraph, rVertex, t);
int max = -1, u, v;
for(i=0;i<m;i++) {
if(edges[i].c > max) {
u = edges[i].u;
v = edges[i].v;
if(vertex[u].key != Integer.MAX_VALUE && rVertex[v].key != Integer.MAX_VALUE) {
if(vertex[u].key + rVertex[v].key + edges[i].c <= p)
max = edges[i].c;
}
}
}
out.printLine(max);
}
}
class Edges {
int u, v;
int c;
public Edges(int u, int v, int c) {
this.u = u;
this.v = v;
this.c = c;
}
}
public void Dijkstra(List<Edge> graph[], Vertex a[], int source) {
a[source].key = 0;
PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();

while (!pq.isEmpty()) {
Vertex u = pq.poll();
if(!u.visited) {
u.visited = true;
for(Edge e : graph[u.index]) {
Vertex v = e.dest;
if(v.key > u.key + e.cost) {
//v.parent = u.index;
v.key = u.key + e.cost;
}
}
}
}
}
class Vertex implements Comparable<Vertex> {
public boolean visited;
public int parent, key, index, indexInHeap;
public List<Edge> edges;
public Vertex(int index) {
this.index = index;
visited = false;
parent = -1;
key = Integer.MAX_VALUE;
edges = new ArrayList<Edge>();
indexInHeap = index;
}

public int compareTo(Vertex o) {
return this.key - o.key;
}
}
class Edge {
public Vertex dest;
public int cost;
public Edge(Vertex dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}

}
``````

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

### Re: 12047 : Highest Paid Toll getting TLE in java

Use c++
Check input and AC output for thousands of problems on uDebug!

phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

### Re: 12047 : Highest Paid Toll getting TLE in java

Thanks for your reply. I agree i could have got Accepted in c++, but then I saw 35 odd java submissions with Accepted. So I thought that it is possible to get Accepted in java as well, and my code is not time efficient as it could be. So I posted it here

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

### Re: 12047 : Highest Paid Toll getting TLE in java

Looking at the stats at:http://uva.onlinejudge.org/index.php?op ... ategory=24 currently show 36 Java submissions, not 36 AC Java submissions. Looking at uhunt, out of the last 500 submissions on this problem I can see there were 33 Java submissions and none of them were AC (26 of them were TLE).
Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

### 12047 - Highest Paid Toll

I am getting tle . My algo is, first I calculated all the shortest paths from source. Then, while calculating from target, if (dist[s]+w+dist[target][v] < =p ) than I updated the value of toll. Why TLE? here's my code

Code: Select all

``````#include <iostream>
#include <bits/stdc++.h>
#define inf 1000000
using namespace std;
typedef pair<int,int> ii;
int p,target;
vector<int> dist[2];
int dijkstra(int s,int x)
{

if(x == 0)
else

dist[x][s] = 0;
int maxtoll=-1;
priority_queue<ii> pq;
pq.push({0,s});
while(!pq.empty())
{
int u=pq.top().second,d=pq.top().first; pq.pop();
if(d>dist[x][u]) continue;
{
if(x == 1)
if(dist[0][v]+w+d<=p && w>maxtoll)
maxtoll = w;
if((dist[x][u]+w) < dist[x][v] )
{

dist[x][v] = dist[x][u]+w;
pq.push({dist[x][v],v});
}
}
}
return maxtoll;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,m,s; scanf("%d%d%d%d%d",&n,&m,&s,&target,&p);
for(int i=0;i<=n;++i){
}
dist[0].assign(n+2,1000000);
dist[1].assign(n+2,1000000);
while(m--)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);

}
dijkstra(s,0);
printf("%d\n",dijkstra(target,1));

}

}
``````

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

### Re: 12047- Getting TLE in C++

These lines are slow:

Code: Select all

``````    while(t--){
for(int i=0;i<=n;++i){
}
dist[0].assign(n+2,1000000);
dist[1].assign(n+2,1000000);``````
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 12047 - Highest Paid Toll - Getting Wrong Answer

AC
Last edited by moxlotus on Sun Jan 11, 2015 12:34 pm, edited 1 time in total.

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 12047 - Highest Paid Toll

AC
Last edited by moxlotus on Sat Feb 07, 2015 7:21 am, edited 1 time in total.

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

### Re: 12047 - Highest Paid Toll

It looks like you figured it out
Check input and AC output for thousands of problems on uDebug!