xxx游戏
Time Limit: 1000MS Memory Limit: 32768 KB
Description
小M最近很喜欢玩XXX游戏。这个游戏很简单,仅由3个场景(分别为1、2、3)构成构成,只存在1->2、2->3、3->1的路径,三条路径的时间花费都是1个小时。由于剧情需要,这个游戏有N个剧情任务,每个剧情任务在其中一个场景中完成,但是某些剧情的触发前提是一些必要剧情任务已经完成。为了简化问题,每个剧情任务都只需要一个小时就可以完成。小M想要花最少的时间通关,然而他还有很多考试,所以请你计算出通关所需要的最少时间。一开始,你可以选择1、2、3其中一个场景开始做任务。
Input
第一行为整数T(T
Output
最少时间数。
Sample Input
2
1
1
0
5
2 2 1 1 3
1 5
2 5 1
2 5 4
1 5
0
Sample Output
1
7
思路:
枚举三个场景为起点的情况,对于每个情况,对每个场景模拟一次拓扑排序,得到最小时间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef __int64 LL;
vector<int>itv[5],edge[250];
int Indegree[250];
int In[250];
int id[250];
int solve(int x)
{
int res = 0;
queue<int>que[5];
for (int i = 0;i < 250;i++)
{
In[i] = Indegree[i];
}
for (int i = 1;i <= 3;i++)
{
for (int j = 0;j < itv[i].size();j++)
{
if (In[itv[i][j]] == 0)
{
que[i].push(itv[i][j]);
}
}
}
for (int i = x;;i++)
{
i %= 3;
if (i == 0) i = 3;
while (!que[i].empty())
{
int val = que[i].front();
que[i].pop();
res++;
for (int j = 0;j < edge[val].size();j++)
{
if (--In[edge[val][j]] == 0)
{
que[id[edge[val][j]]].push(edge[val][j]);
}
}
}
if (que[1].empty() && que[2].empty() && que[3].empty())
{
break;
}
res++;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(Indegree,0,sizeof(Indegree));
memset(id,0,sizeof(id));
for (int i = 0;i < 5;i++)
{
itv[i].clear();
}
for (int i = 0;i < 250;i++)
{
edge[i].clear();
}
int N,cnt,tmp;
scanf("%d",&N);
for (int i = 1;i <= N;i++)
{
scanf("%d",&tmp);
itv[tmp].push_back(i);
id[i] = tmp;
}
for (int i = 1;i <= N;i++)
{
scanf("%d",&cnt);
while (cnt--)
{
scanf("%d",&tmp);
edge[tmp].push_back(i);
Indegree[i]++;
}
}
int res = 0x3f3f3f3f;
for (int i = 1;i <= 3;i++)
{
res = min(res,solve(i));
}
printf("%d\n",res);
}
return 0;
}