P9943 [USACO21FEB] Year of the Cow B 题解

传送门：

• 洛谷
• GMOJ

大意

给出 Farmer John 的农场里每一头牛年龄的关系，求 Bessie 和 Elsie 的年龄相差多少。

解法

先把每头牛的年龄相差算出来，再用类似宽搜的办法算出即可

#include <bits/stdc++.h>
using namespace std;
int n,cnt=1,b[105][105],w[105],a[105][105],vis[105];
map<string,int> mp;
queue<pair<int,int>> q;
int main()
{
	string c1,_,__,t,year,___,____,c2;
	cin >> n;
	mp["Bessie"]=1;
	for (int i = 1 ; i <= n ; ++i)
	{
		cin >> c1 >> _ >> __ >> t >> year >>___ >> ____ >> c2;
		mp[c1]=++cnt;
		if (t=="next")
		{
			b[mp[c2]][cnt]=0;
		} else {
			b[mp[c2]][cnt]=1;
		}
		int tmp=0;
		switch (year[0])
		{
			case 'O': tmp=1; break;
			case 'T': tmp=2; break;
			case 'R': 	if (year[2]=='b') tmp=3;
						else if (year[2]=='o') tmp=9;
						else if (year[2]=='t') tmp=12;
						break;
			case 'D':  	if (year[1]=='r') tmp=4;
						else if (year[1]=='o') tmp=10;
						break;
			case 'S': tmp=5; break;
			case 'H': tmp=6; break;
			case 'G': tmp=7; break;
			case 'M': tmp=8; break;
			case 'P': tmp=11;break;
		}
		a[mp[c2]][cnt]=tmp; 
	}
	q.push({1,1});
	w[1]=0;
	int target=mp["Elsie"];
	while (q.size())
	{
		int x=q.front().first, y=q.front().second;
		q.pop();
		if (x==target) break;
		if (vis[x]) continue;
		vis[x]=1;
		for (int i = 1 ; i <= cnt ; ++i)
		{
			if (a[x][i]!=0)
			{
				if (b[x][i])
				{
					if (a[x][i]==y) w[i]=w[x]-12;
					else if (a[x][i]>y) w[i]=w[x]-(12-(a[x][i]-y));
					else w[i]=w[x]-(y-a[x][i]);
				} else {
					if (a[x][i]==y) w[i]=w[x]+12;
					else if (a[x][i]<y) w[i]=w[x]+(12-(y-a[x][i]));
					else w[i]=w[x]+(a[x][i]-y); 
				}
				q.push({i,a[x][i]});
			}
		}
	}
	cout << abs(w[target]) << endl;
	return 0;
}

神奇的模拟~~