华为oj 字串的连接最长路径查找

这道题应该是初级中最难的了吧，这道题整体思路应该是，把每个字符串看成一个节点，这样我们要求的就是在一个有向图中两点形成的最长路径，对于这种类型的题目，可以考虑采用佛洛依德算法，因为它是查找有向图所有两点之间的路径长度，这样很容易就会找到最长的路径！！！

程序如下：

//弗洛伊德算法求最短路径，动态规划,有待深究
//dp[i,j,k]=min{dp[i,j,k-1],dp[i,k,k-1]+dp[k,j,k-1]}

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main()
{
int dist[100][100], s = 0, n = 0, max = 0, start = 0, end = 0;

string temp,result;
vector<string> in;
int path[100][100];

memset(dist, 0, sizeof(int)*10000);
memset(path, -1, sizeof(int)*10000);

while (cin>>temp)
{
in.push_back(temp);
n++;
}

//初始化有向图
for (int i = 0; i < n; i++)
{
temp = in[i].substr(1,3);
for (int j = 0; j < n; j++)
{
if (i != j)
{
if (in[j].substr(0, 3).compare(temp) == 0)
{
dist[i][j] = 1;
}
}
}
}

//动态规划实现弗洛伊德算法
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (dist[i][k] != 0 && dist[k][j] != 0)
{
if (dist[i][k] + dist[k][j]>dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}

for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (max<dist[i][j])
{
max = dist[i][j];
start = i;
end = j;
}
}
}

temp = "";
result = in[start][0];
int mid = path[start][end];

while (mid >= 0)
{
temp = in[mid][0] + temp;
mid = path[start][mid];
}

result += temp;
result += in[end];

cout << result << endl;
return 0;
}