OJ Board

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

}

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



    }

}

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