LOJ: 1379 - Toll Management (Dijakstra)

- 

LOJ: 1379 - Toll Management
///============================================================================///
///                                                                            ///
///                            IT'S ME                                         ///
///                         BISHAL GAUTAM                                      ///
///                  CSE,JAHANGIRNAGAR UNIVERSITY,DHAKA                        ///
///               "Follow Excellence..Success will chase U"                    ///
///                                                                            ///
///============================================================================///
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>

///==Scanning====///
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
#define SL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

///==Arr,Vec Functions==///
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define MAX(a) (*max_element(all(a)))
#define MIN(a) (*min_element(all(a)))
#define fv(i,v)  for(int i=0;i<(int)v.size();i++)
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define rf(i,n,a) for(int i=n;i>=a;i--)

///===Some Useful====///
#define OnBit(a) __builtin_popcountll((ll)a)
#define LB(v,k) lower_bound(v.begin(),v.end(),k)
#define _cin ios_base::sync_with_stdio(0),cin.tie(0)
#define dbg(x) cerr<<__LINE__<< ":: "<<#x<<"= "<<x<<endl
#define UNIK(v) sort(all(v)),v.resize( unique(all(v)) -v.begin() );
#define fi(n) for(__typeof(n.begin()) it=n.begin();it!=n.end();it++)
#define IO freopen("A.in","r",stdin),freopen("Out.out","w",stdout)
using namespace std;

///===TypeDefs=====///
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<pii> vii;

///===Number Theory===///
//template< class T > inline T SQR(T a) { return ((a)*(a)); }
//template< class T > inline T gcd(T a,T b) {a=abs(a);b=abs(b); if(!b) return a; return gcd(b,a%b);}
//template< class T > inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/_gcd(a,b))*b;}
//template<typename T> T POW(T b,T p) {T r=1; while(p){if(p&1)r=(r*b);b=(b*b);p>>=1;}return r;}
//template<typename T> T BigMod(T b,T p,T m) {T r=1; while(p){if(p&1)r=(r*b)%m;b=(b*b)%m;p>>=1;}return r;}
//template<typename T> T ModInverse(T n,T m) { return BigMod(n,m-2,m); }
//
/////==GeoMetry=========///
//double DEG(double x) { return (180.0*x)/(PI);}
//double RAD(double x) { return (x*(double)PI)/(180.0);}
//template<typename T> double DIS(T a,T b){ return sqrt((double)( SQR(a.X-b.X)+ SQR(a.Y-b.Y))); }
//template<typename T> T ANGLE(T a,T b){ return atan( double(a.Y-b.Y) / double(a.X-b.X));}
//template<typename T> int isLeft(T a,T b,T c) { return (c.X-a.X)*(b.Y-a.Y)-(b.X-a.X)*(c.Y-a.Y); }
//
/////===IO-Related===///
//template< class T > void prnt(T v) { fv(i,v) {if(!i)cout<<v[i];else cout<<" "<<v[i];} cout<<endl; }
//template< class T > void BIN(T n) { if(!n){nl;return;}BIN(n/2);cout<<(n%2); }

///====Some-Stuff===///
// atoi( str.c_str() ); // char string to int
/// sprintf(str,"%d",num);// num to char string
///int month[]={-1,31,28,31,30,31,30,31,31,30,31,30,31}; //Not Leap Year
///int dx[]= {1,0,-1,0};int dy[]= {0,1,0,-1}; //4 Direction
///int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 Direction
///int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction

/**************************************************************************************
 * ///////////////////////////////////////////////////////////////////////////////////*
 *************************************************************************************/

///==========CONSTANTS==============///
///  Digit     0123456789*#@%&^$"-  ///
#define MX     100005
#define inf    1000000000
#define MD     1000000007LL
#define eps    1e-9
///================================///

vector<int>G[MX+2];
vector<int>C[MX+2];
vector<int>GG[MX+2];
vector<int>CC[MX+2];
int dis[2][MX+2];

void Djk(int x,int *dis) {
    for(int i=0; i<MX; i++)dis[i]=inf;
    priority_queue< pii, vector<pii> ,greater<pii> >PQ;
    PQ.push( mpp(x,0) );
    dis[ x ]=0;
    while( !PQ.empty() ) {
        pii p=PQ.top();
        PQ.pop();
        int u=p.X;
        int cs=p.Y;
        for( int i=0; i<SZ(G[u]); i++ ) {
            int v=G[u][i];
            int w=C[u][i];
            if( dis[v]>dis[u]+w ) {
                dis[v]=dis[u]+w;
                PQ.push( mpp(v,dis[v] ) );
            }
        }
    }
}

void Djk2(int x,int *dis) {
    for(int i=0; i<MX; i++)dis[i]=inf;
    priority_queue< pii, vector<pii> ,greater<pii> >PQ;
    PQ.push( mpp(x,0) );
    dis[ x ]=0;
    while( !PQ.empty() ) {
        pii p=PQ.top();
        PQ.pop();
        int u=p.X;
        int cs=p.Y;
        for( int i=0; i<SZ(GG[u]); i++ ) {
            int v=GG[u][i];
            int w=CC[u][i];
            if( dis[v]>dis[u]+w ) {
                dis[v]=dis[u]+w;
                PQ.push( mpp(v,dis[v] ) );
            }
        }
    }
}

int main() {
    int tc,cs=1,i,j,k,n,m,s,t,p,x,y,z;
    S(tc);
    while(tc--) {
        S2(n,m);
        S3(s,t,p);
        fr(i,1,n)G[i].clear(),C[i].clear();
        fr(i,1,n)GG[i].clear(),CC[i].clear();
        fr(i,1,m) {
            S3(x,y,z);
            G[x].pb(y);
            GG[y].pb(x);
            C[x].pb(z);
            CC[y].pb(z);
        }
        Djk(s,dis[0]);
        Djk2(t,dis[1]);
        int mx=-1;
        for(i=1; i<=n; i++) {
            for(j=0; j<SZ(G[i]); j++) {
                k=G[i][j];
                z=C[i][j];
                if( (dis[0][i]+dis[1][k]+z)<=p) {
                    mx=max(mx,z);
                }
            }
        }
        printf("Case %d: %d\n",cs++,mx);
    }
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

UVA 11019 - Matrix Matcher( 2D String matching, Rolling Hash )

-
UVA 11019 - Matrix Matcher ( 2D String matching, Rolling Hash ) Problem: Given 2D Text string and 2D pattern string, you have to count how many times 2D pattern occurs in 2D Text. Idea: Rolling Hash, Firstly compute hashes of segement of fixed window on row , then stored it. Then, Taking these Stored hash value as alphabets calculate hash on column on fixed window using rolling hash mechanism. // /==================================================/// // / HELLO WORLD !! /// // / IT'S ME /// // / BISHAL GAUTAM /// // / [ bsal.gautam16@gmail.com ] /// // /==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,in...
Read more

UVA-12062 - Reverse Assignment

-
UVA: 12062 - Reverse Assignment ///============================================================================/// /// /// /// IT 'S ME /// /// BISHAL GAUTAM /// /// CSE,JAHANGIRNAGAR UNIVERSITY,DHAKA /// /// "Follow Excellence..Success will chase U" /// /// /// ///============================================================================/// #include<bits/stdc++.h> #define PI acos(-1.0) #define X first #define Y second #define mpp make_pair #define nl printf("\n") #define SZ(x) (int)(x.size()) #define pb(x) push_back(x) #define pii pair<int,int> #define pll pair<ll,ll...
Read more

HackerRank: Poisonous Plants ( Stacks, DS )

-
HackerRank: Poisonous Plants ( Stack, DS ) (Find me on HackerRank @ Handle: BishalG ) Problem Summary: In this problem, we are given some value , say pesticide levels of each plants. A plant will dies if all plants to its left side have smaller such value than that of its own. We have to calculate the number of days after which no plants will die!! Solution Idea: For every position find out: "How many times it will be hitted from right side", say hits(i) maximum among all hits(i) is the desired answer!! To find this, keep track of values in stack and try to eliminate all values in current stack which are greater than p(i) from each points !! At certain point, if we find element which is to be counted as kth hit counter but that element itself require more than k hits to be stable then, we count that element as hit source of maximum value. In this way, we will not repetitive actions and one element is added and popped from stack at most one time which leads to th...
Read more