编程之美2016复赛题目可参见此处。
简单看了一下题目，发现题目描述中定义了很多符号，不是很清晰，于是先看了看实体属性的定义。官方文档里定义了很多属性，这里我们只需要关注题目中出现的属性即可(以下加粗部分)。
符号与解释
- Id：实体的id号
Ti：论文标题Y：论文发表年份D：论文发表日期CC：被引用次数AA.AuN：作者姓名- AA.AuId：作者的id号
AA.AfN:单位的名称- AA.AfId：单位的id号
F.FN：研究领域的名称- F.FId：研究领域的id号
J.JN：期刊名称- J.JId：期刊的id号
C.CN：会议名称- C.CId：会议的id号
- RId：引用的论文的id号
W：关键字E：扩展的元数据
显然，可以把这里的“实体”理解为论文，所以实体的id就是论文的id。看起来，论文是在哪个会议/哪个期刊发表的，研究领域是什么，作者是谁，引用论文，这些数据都有定义。
详细数据结构
上面的实体属性定义，看起来不是很复杂。结果后来我随便拖了些数据来看，发现有些地方还是有坑的。用struct的方式大致描述一下数据结构(只涉及重要的属性)
struct entity{
int Id;
List RId;
struct Field {
string FN;
int FId;
};
List F;
struct Conference {
string CN;
int CId;
} optional C;
struct Journal {
string JN;
int JId;
} optional J;
struct AuthorOrAffiliation {
string AuN;
int AuId;
string optional AfN;
int optional AfId;
}
List AA;
}
所有标注为optional的字段都是可以没有的。AuId和AfId可能是一对多的关系，即一个作者可能对应多个单位，也可以一个单位也不对应（其实也是很符合实际情况的）。
查询方法
Academic Knowledge API提供了三个查询类型Interpret(翻译)，evaluate(计算)，calchistogram(统计直方图)。可能需要用到的就只有evaluate。
往下面这个网址发送GET请求，就会返回一个结果，为JSON字符串。
其中，{expression}需要被替换成一个查询表达式，形式大概是这样：
expr=Composite(AA.AfId=82880672)&count=10000&attributes=Id,AA.AuId,AA.AfId
意思是，查询这样的论文：作者列表中包含id为82880672对应的单位(其实对应的就是Beihang University)，返回的最大数量为10000个，返回的属性有：论文id，作者id，单位id。
写成SQL语句的形式就是这样：（由于MAG不是关系型数据库，所以写成这种形式不是很恰当）
SELECT TOP 10000 Id, AA.AuId, AA.AfId FROM MAG WHERE AA.AfId=82880672
问题分析
问题是给定MAG中一对实体的标识符，能够找到所有连接它们的1跳，2跳，3跳路径。而且，给定的实体的标识符是[Id, Id], [Id, AA.AuId], [AA.AuId, Id], [AA.AuId, AA.AuId]。
仔细想想，情况也不是很复杂。按输入分类讨论如下：
输入为[Id, Id]，可能的路径：
Id——Id
Id——Id——Id
Id——F.FId——Id
Id——C.CId——Id
Id——J.JId——Id
Id——AA.AuId——Id
Id——Id——Id——Id
Id——Id——F.FId——Id
Id——Id——C.CId——Id
Id——Id——J.JId——Id
Id——Id——AA.AuId——Id
Id——F.FId——Id——Id
Id——C.CId——Id——Id
Id——J.JId——Id——Id
Id——AA.AuId——Id——Id
输入为[AA.AuId, AA.AuId]，可能的路径：
AA.AuId——Id——AA.AuId
AA.AuId——AA.AfId——AA.AuId
AA.AuId——Id——Id——AA.AuId
输入为[Id, AA.AuId]，可能的路径：
Id——AA.AuId
Id——Id——AA.AuId
Id——Id——Id——AA.AuId
Id——F.FId——Id——AA.AuId
Id——C.CId——Id——AA.AuId
Id——J.JId——Id——AA.AuId
Id——AA.AuId——Id——AA.AuId
Id——AA.AuId——AA.AfId——AA.AuId
输入为[AA.AuId, Id]，可能的路径：
AA.AuId——Id
AA.AuId——Id——Id
AA.AuId——Id——Id——Id
AA.AuId——Id——F.FId——Id
AA.AuId——Id——C.CId——Id
AA.AuId——Id——J.JId——Id
AA.AuId——Id——AA.AuId——Id
AA.AuId——AA.AfId——AA.AuId——Id
由于数据量巨大，所以两跳和三跳的情况只能从两头往中间查找。