2013
12-12

# Idiomatic Phrases Game

Tom is playing a game called Idiomatic Phrases Game. An idiom consists of several Chinese characters and has a certain meaning. This game will give Tom two idioms. He should build a list of idioms and the list starts and ends with the two given idioms. For every two adjacent idioms, the last Chinese character of the former idiom should be the same as the first character of the latter one. For each time, Tom has a dictionary that he must pick idioms from and each idiom in the dictionary has a value indicates how long Tom will take to find the next proper idiom in the final list. Now you are asked to write a program to compute the shortest time Tom will take by giving you the idiom dictionary.

The input consists of several test cases. Each test case contains an idiom dictionary. The dictionary is started by an integer N (0 < N < 1000) in one line. The following is N lines. Each line contains an integer T (the time Tom will take to work out) and an idiom. One idiom consists of several Chinese characters (at least 3) and one Chinese character consists of four hex digit (i.e., 0 to 9 and A to F). Note that the first and last idioms in the dictionary are the source and target idioms in the game. The input ends up with a case that N = 0. Do not process this case.

One line for each case. Output an integer indicating the shortest time Tome will take. If the list can not be built, please output -1.

5
5 12345978ABCD2341
5 23415608ACBD3412
7 34125678AEFD4123
15 23415673ACC34123
4 41235673FBCD2156
2
20 12345678ABCD
30 DCBF5432167D
0

17
-1

1  只要建好图，然后利用SPFA求解最短路即可。注意字符串的处理
2  定义一个char ch[10]数组，如果给数组的每一个元素值赋值后，还要记得要在最后ch[9]添加‘\0’，表示结束。就是如果要保存10个元素，那么数组最小要开到11，因为第11个表示‘\0’来表示正常结束。所以数组尽量开大点

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF

int n;
char str[MAXN][MAXN];
int value[MAXN][MAXN];
int t[MAXN];
int dis[MAXN];
int vis[MAXN];
queue<int>q;

/*初始化*/
void init(){
int i , j , k , len;
char ch1[10], ch2[10];
for(i = 1 ; i <= n ; i++){
len = strlen(str[i])-4;
for(k = 0 ; k < 4 ; k++)
ch1[k] = str[i][len+k];
ch1[4] = '\0';/*末尾加上'\0'，表示字符串结束*/
for(j = 1 ; j <= n ; j++){
value[i][j] = INF;
for(k = 0 ; k < 4 ; k++)
ch2[k]  = str[j][k];
ch2[4] = '\0';/*末尾加上'\0'，表示字符串结束*/
if(!strcmp(ch1 , ch2))
value[i][j] = t[i];
}
value[i][i] = 0;
}
}

/*SPFA*/
void SPFA(){
memset(vis , 0 , sizeof(vis));
for(int i = 2 ; i <= n ; i++)
dis[i] = INF;
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 1 ; i <= n ; i++){
if(value[x][i] && dis[i] > dis[x] + value[x][i]){
dis[i] = dis[x] + value[x][i];
if(!vis[i]){
vis[i] = 1;
q.push(i);
}
}
}
}
}

int main(){
while(scanf("%d" , &n) && n){
for(int i = 1; i <= n ; i++)
scanf("%d %s" , &t[i] , str[i]);
init();
SPFA();
if(dis[n] != INF)
printf("%d\n" , dis[n]);
else
printf("-1\n");
}
return 0;
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮