12047 - Highest Paid Toll

All about problems in Volume 120. 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
phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

12047 : Highest Paid Toll getting TLE in java

Post by phantom11 » Wed Sep 18, 2013 11:59 am

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();
                graph[a].add(new Edge(vertex[b], c));
                rGraph[b].add(new Edge(rVertex[a], c));
                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>();
        pq.add(a[source]);

        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;
                        pq.add(v);
                    }
                }
            }
        }
    }
    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

Post by brianfry713 » Thu Sep 19, 2013 1:18 am

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

Post by phantom11 » Thu Sep 19, 2013 7:54 am

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

Post by brianfry713 » Thu Sep 19, 2013 9:41 pm

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

Post by tamim1382csedu19 » Tue Oct 29, 2013 10:09 am

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<ii> adjls[10005];
vector<ii> adjlt[10005];
vector<int> dist[2];
int dijkstra(int s,int x)
{

    vector<ii> *adjl;
    if(x == 0)
        adjl=adjls;
    else
        adjl=adjlt;

    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;
        for(int j=0;j<adjl[u].size();++j)
        {
            int v=adjl[u][j].first,w=adjl[u][j].second;
            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){
        adjls[i].clear();
        adjls[i].reserve(100005);
        adjlt[i].clear();
        adjlt[i].reserve(100005);
        }
    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);
        adjls[u].push_back({v,c});
        adjlt[v].push_back({u,c});

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



    }

}
here's ideone link http://ideone.com/RoxYGd

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

Re: 12047- Getting TLE in C++

Post by brianfry713 » Tue Oct 29, 2013 10:23 pm

These lines are slow:

Code: Select all

    while(t--){
    for(int i=0;i<=n;++i){
        adjls[i].clear();
        adjls[i].reserve(100005);
        adjlt[i].clear();
        adjlt[i].reserve(100005);
        }
    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

Post by moxlotus » Sat Jan 03, 2015 6:41 am

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

Post by moxlotus » Sun Jan 11, 2015 11:09 am

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

Post by brianfry713 » Tue Jan 13, 2015 12:08 am

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

Post Reply

Return to “Volume 120 (12000-12099)”