UVa 10806 - Dijkstra, Dijkstra.

/*

    Accepted

    Handle conditions properly and try to make optimize
    Dijkstra to avoid TLE

    At first, I have run Dijkstra to find the minimum time is taken by first friend.
    Then, mark parent and child so that second friend can't visit those nodes.
    And finally, again run Dijkstra to find minimum time for the second friend if possible.
    Answer should be summation of both times.

*/


#include<bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fast ios_base::sync_with_stdio(false)

typedef long long LL;

const int high = 110;
const int inf = (1<<31)-1;

struct data
{
    int node, cost;
    data(){ }
    data(int n, int c)
    {
        node = n;
        cost = c;
    }
    bool operator<(const data &b)const
    {
        return cost>b.cost;
    }
};

vector<data>adj[high];

int visited[high][high], par[high], min_cost[high];

void CLR(int n)
{
    for(int i=1;i<=n;i++)
    {
        adj[i].clear();

        for(int j=1;j<=n;j++)
        {
            visited[i][j]=0;
        }
    }
}

void Dijkstra(int s, int d, int n)
{
    int i, j, w, u, v;

    for(i=1;i<=n;i++)
    {
        min_cost[i]=inf;
    }

    min_cost[s] = 0;

    priority_queue<data>Q;

    Q.push(data(s, 0));

    while(!Q.empty())
    {
        u = Q.top().node;
        w = Q.top().cost;

        Q.pop();

        //cout << "u = " << u << " cost = " << min_cost[u] << "\n";

        if(u==d) return;

        //if(w > min_cost[u]) continue;

        int sze = adj[u].size();

        for(i=0;i<sze;i++)
        {
            v=adj[u][i].node;
            int cc = adj[u][i].cost + w;

            if(visited[u][v] || cc>=min_cost[v])
            {
               continue;
            }

             min_cost[v]=cc;
             Q.push(data(v,cc));
             par[v]=u;
        }
    }
}

void CantVisit(int n)
{
    for(int i=n; i!=1; i=par[i])
    {
       int tmp = par[i];

       visited[tmp][i]=1; // mark parent and child node so that further it may not visit

        for(int j=0;j<adj[i].size();j++)
        {
           int v = adj[i][j].node;

            if(v == tmp)
            {
               adj[i][j].cost *= -1;
            }
        }
    }
}

int main()
{
    //freopen("input_test.txt", "r", stdin);
    //freopen("input.txt", "r", stdin);

    //cout << inf;

    int n, m, i, j, u,v,c;

    while(sf("%d",&n)==1)
    {
        if(n==0) break;

        CLR(n);

        sf("%d",&m);

        for(i=0;i<m;i++)
        {
            sf("%d %d %d", &u, &v, &c);

            adj[u].push_back(data(v,c));
            adj[v].push_back(data(u,c));
        }

        long long total = 0;

        Dijkstra(1, n, n);

        if(min_cost[n]==inf)
        {
            pf("Back to jail\n");
            continue;
        }

        total += min_cost[n];

        //cout << total << "\n";

        CantVisit(n);

        Dijkstra(1, n, n);

        if(min_cost[n]==inf)
        {
            pf("Back to jail\n");
            continue;
        }

        total += min_cost[n];

        pf("%lld\n", total);
    }

    return 0;
}