21. 成语接龙-Toy模板网

这篇具有很好参考价值的文章主要介绍了21. 成语接龙。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

小张非常喜欢与朋友们玩成语接龙的游戏，但是作为“文化沙漠”的小张，成语的储备量有些不足。现在他的大脑中存储了m个成语，成语中的四个汉字都用一个1000000以内的正整数来表示。现在小张的同学为了考验他给出了他一个成语做开头和一个成语做结尾，如果小张能通过成语接龙的方式说到结尾的成语，他就能够成功完成游戏。他想知道最少能说几个成语能够成功完成游戏。

21. 成语接龙,北理工程设小学期,算法,c++,图论

解题思路：

正解bfs

其他方法：

我们可以不用考虑成语中间的两个数字，如果使用这个成语来进行接龙，我们就相当于从成语的第一个数字通过一条路走到了另一个数字，这样的话每一个成语就相当于一条从成语第一个数字到结尾数字的一条路，因此直接用最短路模型求最短路即可。

这里需要注意我们再求的时候要特判开头成语和结尾成语是否是一个，如果是，输出1，否则以第一个成语的结尾为起点，最后一个成语的开头为终点，计算最短路，再加上开头结尾的2.

代码：文章来源地址https://www.toymoban.com/news/detail-706922.html

#include <cstring>  
#include <iostream>  
#include <algorithm>  
#include <queue>  
#include <map>  
#include <vector>  
using namespace std;  
int n, m;  
const int N = 1000010;  
int h[N], w[N], e[N], ne[N], idx;  
int dist[N];  
bool st[N];  
int s[4],ed[4];  
void add(int a, int b, int c)  
{  
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;  
}  
  
int spfa()  
{  
    memset(dist, 0x3f, sizeof dist);  
    dist[s[3]] = 0;  
    st[s[3]] = true;  
    queue<int> q;  
    q.push(s[3]);  
    while (q.size())  
    {  
        int t = q.front();  
        st[t] = false;  
        q.pop();  
        for (int i = h[t]; i != -1; i = ne[i])  
        {  
            int j = e[i];  
            if (dist[j] > dist[t] + w[i])  
            {  
                dist[j] = dist[t] + w[i];  
                if (!st[j])  
                {  
                    st[j] = true;  
                    q.push(j);  
                }  
            }  
        }  
    }  
    return dist[ed[0]];  
}  
int main()  
{  
    memset(h, -1, sizeof h);  
    ios::sync_with_stdio(false);  
    cin.tie(0);  
    cout.tie(0);  
    int n;  
    cin>>n;  
    int x[4];  
    for(int i=1;i<=n;i++){  
        cin>>x[0]>>x[1]>>x[2]>>x[3];  
        add(x[0],x[3],1);  
    }  
    for(int j=0;j<=3;j++){  
        s[j]=0;  
        cin>>s[j];  
        //cout<<s[j]<<endl;  
    }  
    for(int j=0;j<=3;j++){  
        ed[j]=0;  
        cin>>ed[j];  
    }  
    bool ff=1;  
    for(int j=0;j<=3;j++){  
        //cout<<s[j]<<ed[j];  
        if(s[j]!=ed[j]){  
            ff=0;break;}  
    }  
    if(ff){  
        cout<<1<<endl;  
        return 0;  
    }  
    else{  
        spfa();  
    if(dist[ed[0]]<0x3f3f3f3f/2)cout<<dist[ed[0]]+2<<endl;  
    else cout<<-1<<endl;  
    }   
    return 0;  
}

到了这里，关于21. 成语接龙的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！