Light OJ 1074 - Extended Traffic

Problem link - 1074 - Extended Traffic

In this problem we have to compute minimum earning from node 1. At first we have to do a dfs to see if destination is reachable from 1.Every node that can be reached with negative earning , all its adjacent nodes can be reached with negative earning too.

If a node if not reachable from 1 or or the earning is less than 3 then we have to print '?' else we have to print ta earning from 1. We can use bellman ford algorithm from this problem as there are negative earnings.

let us analyze some test cases:

1

5

6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

here node 4 (D) can be reached with earning 3 and node 5(E) can be reached with earning 4

4
10 12 15 14
2
1 2
3 4
4
1
2
3
4

here node 3(C) and node 4(D) can't be reached from 1, but 2(B) can be reached with earning 8

	#include<bits/stdc++.h>
	using namespace std;
	int n;
	int busy[205];
	vector<int>v[205];
	vector<int>c[205];
	bool visited[205];
	int cost[205];
	void in_single_source(int s){
	for(int i=1;i<=n;i++){
	cost[i]=INT_MAX/3;
	}
	cost[s]=0;
	}
	void relax(int u,int v,int w){
	if(cost[v]>(cost[u]+w)){
	cost[v]=cost[u]+w;
	}
	}
	bool bellmon_ford(int s){
	in_single_source(s);
	for(int k=1;k<n;k++){
	for(int j=1;j<=n;j++){
	int u=j;
	for(int k=0;k<v[u].size();k++){
	int vp = v[u][k];
	int w = c[u][k];
	relax(u,vp,w);
	}
	}
	}
	bool f=true;
	for(int j=1;j<=n;j++){
	int u=j;
	for(int k=0;k<v[u].size();k++){
	int vp = v[u][k];
	int w = c[u][k];
	if(cost[vp]>cost[u]+w)
	f=false;
	}
	}
	return f;
	}
	void dfs(int x){
	visited[x]=true;
	for(int i=0;i<v[x].size();i++){
	if(visited[v[x][i]]==false){
	dfs(v[x][i]);
	}
	}
	}
	int main(){
	int t;
	cin>>t;
	for(int y=1;y<=t;y++){
	cin>>n;
	for(int j=1;j<=n;j++){
	cin>>busy[j];
	}
	int m;
	cin>>m;
	for(int j=1;j<=m;j++){
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	int w = (busy[b]-busy[a]);
	c[a].push_back(w*w*w);
	}
	bool p = bellmon_ford(1);
	dfs(1);
	int q;
	cin>>q;
	printf("Case %d:\n",y);
	while(q--){
	int a;
	cin>>a;
	if(cost[a]>2 && cost[a]<INT_MAX/3 && visited[a]) cout<<cost[a]<<"\n";
	else cout<<"?\n";
	}
	for(int i=0;i<=n;i++){
	v[i].clear();
	c[i].clear();
	}
	memset(cost,0,sizeof(cost));
	memset(busy,0,sizeof(busy));
	memset(visited,0,sizeof(visited));
	}
	return 0;
	}

view raw 1074 - Extended Traffic.cpp hosted with ❤ by GitHub