Orz ! ! ! 传送门
题意：给出若干个字符串，求是否能选用一些字符串连接， 使得新的字符串以 b 开头 ，以 m 结尾 分析： 由于本蒟蒻不会什么DFS，各种奇怪的搜索，所以用 Dijskra 跑了一遍。 假设每一个单词S为：以S[0]-->S[len-1] 边权为1的有向边。就可以套模板了 #include <set> #include <map> #include <cmath> #include <stack> #include <queue> #include <string> #include <vector> #include<cstring> #include <stdio.h> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6+5; struct Edge{ int to,next,val; }edge[maxn]; int head[maxn],tot,dis[maxn]; char s[maxn]; bool vis[maxn]; void add_edge(int u,int v,int w){ edge[tot].to=v; edge[tot].val=w; edge[tot].next=head[u]; head[u]=tot++; } struct node{ int dis,pos; bool operator<(const node &x)const { return x.dis<dis; } }; bool Dijskra(int s){ memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); priority_queue<node>q; q.push(node{0,s}); dis[s]=0; while (!q.empty()){ int x=q.top().pos; q.pop(); if(vis[x]) continue; vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val) { dis[y] = dis[x] + edge[i].val; if(!vis[y]) q.push(node{dis[y],y}); } } } if(dis[109]!=INF) return true; else return false; } int main() { char ss[100]; while (~scanf("%s",ss)&&ss[0]!='0') { memset(head,-1,sizeof(head)); tot=0; int ln = strlen(ss); if (ln != 1) add_edge(ss[0], ss[ln - 1], 1); while (scanf("%s", s) && s[0] != '0') { int len = strlen(s); if (len == 1) continue; add_edge(s[0], s[len - 1], 1); } if (Dijskra(98)) printf("Yes.\n"); else printf("No.\n"); } return 0; }