KUET IUPC-2019 Problem-G

Problem G-Shortest path

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<long>vec[30005],cost[30005];
long vis[30005]={0},dist[30005],cnt,pp[30005],mp[30005];
void dfs(long uu,long par)
{
    if(vis[uu]==1)
        return;
    vis[uu]=1;
    mp[uu]=cnt;
    for(long ii=0;ii<vec[uu].size();ii++)
    {
        long vv=vec[uu][ii];
        if(vis[vv]==0)
        {
            dist[vv]=dist[uu]+cost[uu][ii];
            dfs(vv,uu);
        }
        else if(vv!=par){
            long tot=dist[uu]+cost[uu][ii];
            pp[cnt]=max(pp[cnt],tot);
            return;
        }
    }
}
main()
{
    timesave;
    long ts,cs=1;
    scanf("%ld",&ts);
    while(ts--)
    {
        long n,e,i,u,v,w;
        scanf("%ld%ld",&n,&e);
        for(i=1;i<=e;i++)
        {
            scanf("%ld%ld%ld",&u,&v,&w);
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
        }
        cnt=1;
        for(i=1;i<=n;i++)
        {
            if(vec[i].size()==1&&vis[i]==0)
            {
                dist[i]=0;
                dfs(i,0);
                cnt++;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                dist[i]=0;
                dfs(i,0);
                cnt++;
            }
        }
        long q,x,y,ans;
        printf("Case %ld:\n",cs++);
        scanf("%ld",&q);
        for(i=1;i<=q;i++)
        {
            scanf("%ld%ld",&x,&y);
            if(mp[x]==mp[y])
            {
                if(pp[mp[x]]>0)
                {
                    long xx=max(dist[x],dist[y])-min(dist[x],dist[y]);
                    ans=min(pp[mp[x]]-xx,xx);
                }
                else
                {
                    ans=max(dist[x],dist[y])-min(dist[x],dist[y]);
                }
                printf("%ld\n",ans);
            }
            else
                printf("-1\n");
        }
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            cost[i].clear();
            vis[i]=0;
            mp[i]=0;
            pp[i]=0;
            dist[i]=0;
        }
    }
}



/*
4 4
1 3 4
2 3 3
1 4 1
2 4 1
*/