U118795 成语游戏(Idiomatic Phrases Game)

题目来源： Zhejiang Provincial Programming Contest 2006, ZOJ2750

Tom 正在玩一种成语接龙游戏。成语是一个包含多个中文字符、具有一定含 义的短语。游戏规则是：给定 Tom 两个成语，他必须选用一组成语，该组成语中 第 1 个和最后一个必须是给定的两个成语。在这组成语中，前一个成语的最后一 个汉字必须和后一个成语的第一个汉字相同。在游戏过程中，Tom 有一本字典， 他必须从字典中选用成语。字典中每个成语都有一个权值 T，表示选用这个成语 后，Tom 需要花时间 T 才能找到下一个合适的成语。你的任务是编写程序，给定 字典，计算 Tom 至少需要花多长时间才能找到一个满足条件的成语组。 输入描述： 输入文件包含多个测试数据。每个测试数据包含一本成语字典。 字典的第 1 行是一个整数 N，0

``` //选择建图的方式真的很重要,偷个懒，用dfs #include #include #include using namespace std; struct Edge { int to,w,next; } edges[1000000]; const int mn=1001; int n,m,w[mn]; char s[100],a[mn][5],b[mn][5];//a记录前4个字母，b记录后4个字母 int vis[mn];//记录一条路径上的结点 int dis[mn];//记录距离 int head[mn]; void add(int i,int j) { edges[m].to=j; edges[m].w=w[i]; edges[m].next=head[i]; head[i]=m++; } void dfs(int i) { for(int j=head[i]; ~j; j=edges[j].next) { int v=edges[j].to; if(dis[v]>dis[i]+edges[j].w) { dis[v]=dis[i]+edges[j].w; vis[v]=1; dfs(v); vis[v]=0; } } } int main() { while(~scanf("%d",&n)&&n) { for(int i=0; i

无