Solution of Light OJ 1049 - One Way Roads

/* Bismillahir Rahmanir Rahim Solution-Using DFS Apply DFS from the first node in two way & get the minimum */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[101], cost[101]; int sts[101][101], vis[101], ans, st, en; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(at==1){ // its for the first node, use only one way(st) int v=vt[at][st]; // here st=0 or 1 if(!vis[v]){ if(sts[at][v]) // if(redirecting road) ans=ans+cost[at][st]; en=v; // saving the last node of the DFS dfs(v); } } else{ for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(!vis[v]){ if(sts[at][v]) ans=ans+cost[at][j]; // same en=v; // same as before dfs(v); } } } } } int main(){ int t, cs=1, a, b, c, n, a1, a2; cin>>t; while(t--){ cin>>n; fi(1, n){ cin>>a>>b>>c; vt[a].push_back(b); sts[a][b]=0; // normal road vt[b].push_back(a); sts[b][a]=1; // redirecting road cost[a].push_back(c); cost[b].push_back(c); } fi(0, n) vis[i]=0; ans=0, st=1; dfs(1); a1=ans; if(sts[en][1]) a1=a1+cost[1][0]; //if(redirecting road) fi(0, n) vis[i]=0; ans=0, st=0; dfs(1); a2=ans; if(sts[en][1]) a2=a2+cost[1][1]; //same as before ans=min(a2, a1); cout<<"Case "<<cs++<<": "<<ans<<endl; fi(0, n) {vt[i].clear(); cost[i].clear();} } return 0; }