12047 - Highest Paid Toll

[phantom11]

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]

Use c++

[phantom11]

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]

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

[tamim1382csedu19]

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]

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);

[moxlotus]

AC

[moxlotus]

AC

[brianfry713]

It looks like you figured it out