题目：
Idiomatic Phrases GameTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2282Accepted Submission(s): 742
Problem Description
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.
Input
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.
Output
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.
Sample Input
55 12345978ABCD23415 23415608ACBD34127 34125678AEFD412315 23415673ACC341234 41235673FBCD2156220 12345678ABCD30 DCBF5432167D0
Sample Output
17-1
Author
ZHOU, Ran
Source
Zhejiang Provincial Programming Contest 2006
Recommend
linle|We have carefully selected several similar problems for you:13173339124515981531
如果不能从第1个单词到最后一个单词则直接输出-1.否则输出。
题目分析：
这道题其实抽象一下，其实还是最短路的问题。以其他题目不太一样的地方就在于建边规则发生了变化。之前当给出形如"a b c"的数据的时候，就表示a和b之间存在一条边，他们之间的距离是c。而现在，如果a想要和b项链，那么就必须符合“a的后半部分与b的前半部分相同”。
还需要注意的是：
1）inf 取大一点。这里取到了10亿，即1000000000
2）dijkstra算法里面要对没找到最小点的情况处理一下。否则会RE的。
之前总结的模板可能有点漏洞，这道题用到的dijkstra的模板是比较完善的。。
代码如下：
/* * hdu_1546.cpp * * Created on: 2015年3月27日 *Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1015;const int inf = 1000000000;int s[maxn]; //用来记录某一点是否被访问过int map[maxn][maxn]; //地图int dis[maxn]; //从原点到某一个点的最短距离(一开始是估算距离)int n;int target;int val[maxn];char strss[maxn][maxn];/** * 返回从v—->到target的最短路径 */int dijkstra(int v) {int i;for (i = 1; i <= n; ++i) { //初始化s[i] = 0; //一开始，所有的点均为被访问过dis[i] = map[v][i];}dis[v] = 0;//***把自己到自己的距离设成0s[v] = true;//将源点标记为已经访问过..for (i = 1; i < n; ++i) {int min = inf;int pos = -1;int j;for (j = 1; j <= n; ++j) { //寻找目前的最短路径的最小点if (!s[j] && dis[j] < min) {min = dis[j];pos = j;}}//****这里一定要对没有找到最小点的情况处理一下.否则有的题目会跪的。例如HDU 1546.if(pos == -1){//如果诶有找到最小点break;//则跳出循环}s[pos] = 1;for (j = 1; j <= n; j++) { //遍历u的所有的邻接的边if (!s[j] && dis[j] > dis[pos] + map[pos][j]) {dis[j] = dis[pos] + map[pos][j]; //对边进行松弛}}}return dis[target];}int main() {while (scanf("%d", &n) != EOF, n) {int i;for (i = 1; i <= n; ++i) {scanf("%d %s", &val[i], strss[i]);//把每一个单词的查找时间 及 每个单词的时间输进去}int j;for (i = 1; i <= n; ++i) {for (j = 1; j <= n; ++j) {int len = strlen(strss[i]);/*if(strss[i][0] == strss[j][len-4] && strss[i][1] == strss[j][len-3] &&strss[i][2] == strss[j][len-2] && strss[i][3] == strss[j][len-1]){map[i][j] = val[i];}else{map[i][j] = inf;}*//*** 注意以下的写法和上面的写法的区别在于.上面的写法师用前面来拼接.* 而题目要求的是向下面哪种用后面来拼接的*/if (strss[j][0] == strss[i][len – 4]&& strss[j][1] == strss[i][len – 3]&& strss[j][2] == strss[i][len – 2]&& strss[j][3] == strss[i][len – 1]) {map[i][j] = val[i];//将a与b拼接,这时候花费的是查找a单词的时间} else {map[i][j] = inf;}}}target = n;dijkstra(1);if (n == 1) {//如果节点数是1的时候.printf("-1\n");//直接输出-1} else {//否则,如果节点数>1if(dis[n] == inf){//如果不存在从第一个单词到最后一个单词的拼接方式.(如果不存在从第一个节点到最后一个节点的路径)printf("-1\n");//则输出-1}else{//否则printf("%d\n", dis[n]);//输出从第一个节点到最后一个节点的最短路径}}}return 0;}
，环境不会改变，解决之道在于改变自己。
