题目：
5 5 12345978ABCD2341 5 23415608ACBD3412 7 34125678AEFD4123 15 23415673ACC34123 4 41235673FBCD2156 2 20 12345678ABCD 30 DCBF5432167D 0
17 -1
题目大意：
给定一些单词，前一个的尾和后一个的头相同时，才表示他们相连。求从第1个单词到第n个单词的最短路。
如果不能从第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;//***把自己到自己的距离设成0
s[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 {//否则,如果节点数>1
if(dis[n] == inf){//如果不存在从第一个单词到最后一个单词的拼接方式.(如果不存在从第一个节点到最后一个节点的路径)
printf("-1\n");//则输出-1
}else{//否则
printf("%d\n", dis[n]);//输出从第一个节点到最后一个节点的最短路径
}
}
}
return 0;
}
(dijkstra 1.1)hdu 1546 Idiomatic Phrases Game(dijkstra——当建图规则为：当一个单词的后4个字符和另一个单词的前4个字符一致时才建边，求最短路径)
原文：http://blog.csdn.net/hjd_love_zzt/article/details/44679567