OJ Board

Code: Select all

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <stack>

#define INF 800000010
using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef pair<int,ii> iii;
typedef vector<iii> viii;
typedef vector<ii> vii;


vi topo;
int dist[110];
bool visited[110];
vii AdjList[110];

int xtr[4]={0,0,1,-1};
int ytr[4]={1,-1,0,0};
int maksimum(int a,int b)
{
	if (a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

void toposort(int u)
{
	visited[u]=1;
	for (int i=0;i<AdjList[u].size();i++)
	{
		int S=AdjList[u][i].first;
		if (!visited[S])
		{
			toposort(S);
		}
	}
	topo.push_back(u);
}

int main()
{
	int TC,maks;
	int u,v,weight;
	char inp,term;
	scanf("%d",&TC);
	getchar();
	getchar();
	for (int b=1;b<=TC;b++)
	{
		if (b!=1) printf("\n");
		
		//Inisialisasi
		for (int i=1;i<=60;i++)
		{
			AdjList[i].clear();
		}
		for (int i=1;i<=60;i++)
		{
			visited[i]=0;
			dist[i]=0;
		}
		maks=0;
		inp=getchar();
		while ((inp!='\n'))
		{
			//printf("%c\n",inp);
			u=(int)inp-64;
			getchar();
			scanf("%d",&weight);
			term=getchar();
			AdjList[u].push_back(ii(u+30,weight));
			if (term!='\n')
			{
				inp=getchar();
				while ((inp!='\n') && (inp!=EOF))
				{
					v=(int)inp-64;
					AdjList[u+30].push_back(ii(v,0));
					inp=getchar();
				}
			}
			if (inp==EOF)
			{
				break;
			}
			else
			{
				inp=getchar();
			}
		}

		//topological sort
		for (int i=1;i<=60;i++)
		{
			if (!visited[i])
			{
				toposort(i);
			}
		}

		for (int i=topo.size()-1;i>=0;i--)
		{
			int cur=topo[i];
			for(int j=0;j<AdjList[cur].size();j++)
			{
				int S=AdjList[cur][j].first;
				int we=AdjList[cur][j].second;
				dist[S]=maksimum(dist[S],dist[cur]+we);
			}
		}
		for (int i=31;i<=60;i++)
		{
			if (maks<dist[i])
			{
				maks=dist[i];
			}
		}
		printf("%d\n",maks);
	}
	return 0;
}