DAG 2

#include <bits/stdc++.h>

using namespace std;

int vis[100], cost[100], weight[100][100], par[100];
vector <int> connectedNodes[100];
stack <int> ans;

void topodfs(int x)
{
    vis[x]=1;
    for(int i=0; i<connectedNodes[x].size(); i++)
    {
        if(!vis[connectedNodes[x][i]])
        {
            topodfs(connectedNodes[x][i]);
        }
    }
    ans.push(x);
}

void printPath(int x)
{
    if(par[x]==x)return;
    printPath(par[x]);
    printf("%d -> ", par[x]);
    return;
}

int main()
{
    int n, v, x, y, i, s;
    printf("Enter the node number: ");
    scanf("%d", &n);
    printf("Enter the weight number: ");
    scanf("%d", &v);
    memset(vis, 0, sizeof(vis));
    for(i=0; i<v; i++)
    {
        printf("Connection Between: ");
        scanf("%d %d", &x, &y);
        connectedNodes[x].push_back(y);
        printf("Connection Cost: ");
        scanf("%d", &weight[x][y]);
    }
    for(i=0; i<v; i++)
    {
        if(!vis[i])topodfs(i);
    }
    printf("Enter The Source: ");
    scanf("%d", &s);
    for(i=0; i<n; i++)
    {
        if(i==s)
        {
            cost[i]=0;
            par[s]=s;
        }
        else
        {
            cost[i]=10000;
            par[i]=-1;
        }
    }
    while(!ans.empty())
    {
        int node = ans.top();
        ans.pop();
        for(i=0; i<connectedNodes[node].size(); i++)
        {
            if(cost[connectedNodes[node][i]] > cost[node]+weight[node][connectedNodes[node][i]])
            {
                cost[connectedNodes[node][i]]=cost[node]+weight[node][connectedNodes[node][i]];
                par[connectedNodes[node][i]]=node;
            }
        }
    }
    for(i=0; i<n; i++)
    {
        printf("Node %d:\n ", i);
        if(par[i]!=-1)
        {
            printf("Path: Start -> ");
            printPath(i);
            printf("%d\t\t\t", i);
            printf("Cost: %d\n", cost[i]);
        }
        else printf("Cannot Reach\n");
    }
    return 0;
}