12047 - Highest Paid Toll Solution

Problem Link: here

Description:

একটি ডিরেক্টেড ওয়েটেড গ্রাফ দেয়া আছে। s হচ্ছে সোর্স , t = ডেসটিনেশন, cost limit = p.

s থেকে t তে এমন একটা ভ্যালিড পথে যেতে হবে যেখানে একটা edge এর ওয়েট সর্বোচ্চ হবে। ভ্যালিড পথ হতে হলে 

s থেকে  t তে পাথ থাকতে হবে এবং পাথের টোটাল cost ,p এর সমান বা ছোট হতে হবে।

solution: here

#include<bits/stdc++.h>
using namespace std;
#define MX 10005
#define pii pair<int,int>
#define pip pair<int,pii>
vector<pii> adj[MX];
vector<pii> adj2[MX];
vector <pip> ed;
int dis[MX];
int dis2[MX];
int limit;
void Djakstra(int s)
{
    priority_queue <pii> PQ;
    PQ.push(pii(0,s));
    while(!PQ.empty())
    {
        int u = PQ.top().second;
        PQ.pop();
        for (int i=0; i<adj[u].size(); i++)
        {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dis[u]+w < dis[v])
            {
                dis[v] = dis[u]+w;
                PQ.push(pii(-dis[v],v));
            }
        }
    }
}


void Djakstra2(int s)
{
    priority_queue <pii> PQ;
    PQ.push(pii(0,s));
    while(!PQ.empty())
    {
        int u = PQ.top().second;
        PQ.pop();
        for (int i=0; i<adj2[u].size(); i++)
        {
            int v = adj2[u][i].first;
            int w = adj2[u][i].second;
            if (dis2[u]+w < dis2[v])
            {
                dis2[v] = dis2[u]+w;
                PQ.push(pii(-dis2[v],v));
            }
        }
    }
}

int main()
{
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        int node,edge,src,dsn;
        scanf("%d%d%d%d%d",&node,&edge,&src,&dsn,&limit);
        int i;
        for (i=0; i<edge; i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            adj[u].push_back(pii(v,cost));
            adj2[v].push_back(pii(u,cost));
            ed.push_back(pip(cost,pii(u,v)));
        }

        for (i=0;i<=node; i++)
        {
            dis[i] = 100000000;
            dis2[i] = 100000000;
        }
        dis[src]=0;
        Djakstra(src);
        dis2[dsn]=0;
        Djakstra2(dsn);
        //cout<<"dis of des "<<dis[dsn]<<endl;
        int mx = -1;
        for (i=0; i<edge; i++)
        {
            int cost = ed[i].first;
            int u = ed[i].second.first;
            int v = ed[i].second.second;
            if (cost > mx)
            {
                int cost2 = dis[u]+cost+dis2[v];
                if (cost2 <= limit) mx = cost;
            }
        }
        cout<<mx<<endl;
        for (i=0; i<=node; i++)
        {
            adj[i].clear();
            adj2[i].clear();
        }
        ed.clear();
    }
    return 0;
}