这道题的题意十分简单：求从 \(k\) 出发到每个点的最长路。
看到最长路这个词，可能一时半会儿没有思路，因为我们平时学习的都是最短路算法。回忆小学学过的一句话“一个负数的绝对值越大，那么它本身的值就越小”，这提示我们将求最长路设法转化为求最短路。
于是便很容易得出转化思路：先对每条边的长度取相反数，再对整个图求最短路，最后再将答案取相反数。可以证明，这样做能确保最长路的正确性。
接下来看求最短路的算法。可能看到“从 \(k\) 出发”就会想到用 dijkstra。但要注意，此时边长为负数，而 dijkstra 不能处理此类情况，因此不能使用。看到原题 \(n \le 100\)，数据范围不大，因此适宜用 Floyd 来求。
Floyd 的实现（会用的可以跳过）
Floyd 本质上是一种动态规划。设 \(d_{i,j}\) 表示从 \(i\) 到 \(j\) 的最短路径的长度（注意题目输入为有向边，所以 \(d_{i,j}\) 与 \(d_{j,i}\) 的意义不一样），\(n\) 为最大点的编号。
初始时，若 \(i\) 到 \(j\) 之间存在有向边，那么 \(d_{i,j}=1\)（表示 \(i\) 和 \(j\) 之间有一条长度为 \(1\) 的边），否则给 \(d_{i,j}\) 赋予一个大数即可（表示 \(i\)、\(j\) 之间没有直接连接，注意不要太大了，避免超出范围）。
考虑在求 \(i\) 到 \(j\) 的最短路时，枚举一个中转点 \(k\)，并且计算从 \(i\) 到 \(k\)，从 \(k\) 到 \(j\) 的最短路径之和，并用此更新 \(d_{i,j}\)，可以得到如下转移方程：
\[d_{i,j}=\min(d_{i,j},d_{i,k}+d_{k,j}) \]注意在实现 Floyd 时，应当先枚举 \(k\)（即中转点），再枚举 \(i\) 和 \(j\)（起点和终点），这样做可以保证 \(d_{i,k}\) 和 \(d_{k,j}\) 都被计算过，从而更新答案。
在本题中，由于是求最长路，所以要对原始的 Floyd 做一些改动，如上文所述，详细代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
int d[101][101],n,ansa,ansb,t,T,kk;
int main()
{
while(true)
{
T++;
cin>>n;
if(n==0) break;
cin>>kk;
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
d[i][j]=0x3f3f3f3f;
int a,b;
ansa=0,ansb=0;
while(true)
{
cin>>a>>b;
if(a==0&&b==0) break;
d[a][b]=-1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<=n;i++)
if(d[kk][i]<ansa)
{
ansa=d[kk][i];
ansb=i;
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",T,kk,-ansa,ansb);
printf("\n");
}
return 0;
}