PAT甲级1076. Forwards on Weibo

题意：

微博被称为中文版的Twitter。微博上的一位用户可能会有很多关注者，也可能会跟随许多其他用户。因此，社会网络与追随者的关系形成。当用户在微博上发布帖子时，他/她的所有跟随者可以查看和转发他/她的帖子，然后可以由他们的追随者再次转发。

现在给出一个社交网络，假定只计算间接跟随者的L个级别，您应该计算任何特定用户的最大潜在潜在金额。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行包含2个正整数：N（<= 1000），用户数;

和L（<= 6），计数的间接追踪者的数量。因此，假设所有用户的编号从1到N.然后N行遵循，其格式如下：

M [i] user_list [i]

其中M [i]（<= 100）是用户[i]遵循的总人数; user_list [i]是用户[i]遵循的M [i]个用户的列表。

保证没有人能跟随自己。所有的数字都被空格隔开。

然后最后给出肯定的K，然后是K UserID的查询。

输出规格：

对于每个UserID，您应该在一行中打印此用户可以转发的最大潜在数量，

假设每个可以查看初始帖子的人都会转发一次，只计算L个间接追踪者。

思路：

队列bfs或者Dijkstra

ac代码：

C++

// pat1076.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<stdio.h>

#include<map>

#include<cmath>

#include<unordered_map>

#include<unordered_set>

using namespace std;

//visit + dfs会使部分节点提前访问。并不是到源点的最短距离。使得其节点被提前visit，其孩子节点不被统计！！

//队列bfs或者Dijkstra

int n, l;

int mymap[1001][1001];

int res;

int Dijkstra(int x)

{

	int count = -1;

	int len[1001];

	memset(len, -1, sizeof(len));

	len[x] = 0;

	int visit[1001] = { 0 };

	int now;

	while (1)

	{

		now = -1;

		for (int i = 1; i <= n; i++)

		{

			if (!visit[i] && len[i] != -1 && (now == -1 || len[i] < len[now])) now = i;

		}

		if (len[now] > l || now == -1) break;

		visit[now] = 1;

		count++;

		for (int i = 1; i <= n; i++)

		{

			if (mymap[now][i] && !visit[i] && (len[now] + mymap[now][i] < len[i] || len[i] == -1))

			{

				len[i] = len[now] + mymap[now][i];

			}

		}

	}

	return count;

}

int main()

{

	int m, tempfan;

	scanf("%d %d", &n, &l);

	memset(mymap, 0, sizeof(mymap));

	for (int i = 1; i <= n; i++)

	{

		scanf("%d", &m);

		while (m--)

		{

			scanf("%d", &tempfan);

			mymap[tempfan][i] = 1;

		}

	}

	int query;

	scanf("%d", &m);

	for (int i = 0; i < m; i++)

	{

		scanf("%d", &query);

		int res = Dijkstra(query);

		printf("%d\n", res);

	}

    return 0;

}