ACMclub - 1124 成语接龙 （最短路，SPFA）

本文主要是介绍ACMclub - 1124 成语接龙 （最短路，SPFA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接

给出N个字符串，要将字符串处理分离出前4个字符和后4个字符，然后建图。

由于N最大是1000，O（N^2）是可以接受的，所以直接查找前面的点，判断是否符合条件了。不过还可以用HASH吧，这样时间复杂度会小很多，主要是SPFA的时间了，由于SPFA不太熟悉，不然用Bellman-Ford或者Dijkstra在这题的数据都可以的，不过Bellman-ford的O（NM）就有点危险了。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int const MAXN = 1001, MAXM = MAXN*MAXN/2;
int N, T, m;
int first[MAXN], nexte[MAXM];
char s[1000];
struct Edge
{int u, v, w;
}e[MAXM];
struct P
{int w;char s1[5], s2[5];
}p[MAXN];int d[MAXN];
void SPFA(int s)
{queue<int> que;bool inq[MAXN];memset(d, 0x3f, sizeof(d));memset(i

这篇关于ACMclub - 1124 成语接龙 （最短路，SPFA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---