CareerCup

Its simple!!

Let the starting node be start.

1. Go to the next right node of start. Let the node be right_node
2. Go to the extreme left node of right_node. Let this node be extreme_left

Thus this extreme_left node is the inorder successor of start.

#include<cstdio>
#include<vector>
#include<climits>
#define min(a,b) (a<b?a:b)
#define MAXLEN 100
using namespace std;

int find_min(int dist[],bool visited[],int n)
{
    int i,mx,m;
    mx = INT_MAX;
    for(i=0;i<n;i++)
    {
        if(dist[i]<mx && !visited[i])
        {
            mx = dist[i];
            m = i;
        }
    }
    return m;
}

int find_res(int start,int target,int graph[][MAXLEN],int n)
{
    int u,v,w,dist[MAXLEN],cnt,i,j;
    bool visited[MAXLEN];

    for(i=0;i<n;i++)
    {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    dist[start] = 0;
    for(cnt = 1;cnt<n;cnt++)
    {
        u = find_min(dist,visited,n);
        visited[u] = true;
        for(v=0;v<n;v++)
        {
            if(graph[u][v]!=-1 && !visited[v] && dist[u]+graph[u][v]<dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist[target];
}

int minCost(int node,vector<int> from,vector<int> to,vector<int> wt,int start,int target,int weight)
{
    int res,graph[MAXLEN][MAXLEN],i,j;

    start--;
    target--;
    for(i=0;i<node;i++)
    {
        for(j=0;j<node;j++)
            graph[i][j] = -1;
    }
    for(i=0;i<from.size();i++)
    {
        from[i]--;
        to[i]--;
        graph[from[i]][to[i]] = graph[to[i]][from[i]] = wt[i];
    }

    res = find_res(start,target,graph,node);
   // printf("res = %d\n",res);
    for(i=0;i<node;i++)
    {
        for(j=0;j<node;j++)
        {
            if(graph[i][j]==-1)
            {
                graph[i][j] = weight;
                res = min(find_res(start,target,graph,node),res);
                graph[i][j] = -1;
            }
        }
    }
    return res;
}

int main()
{
    int node,edge,a,b,w,i,st,target;
    vector<int> to,from,wt;

    scanf("%d%d",&node,&edge);
    for(i=0;i<edge;i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        to.push_back(a);
        from.push_back(b);
        wt.push_back(w);
    }

    scanf("%d%d%d",&st,&target,&w);
    printf("%d\n",minCost(node,from,to,wt,st,target,w));
    return 0;
}