题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1750
题目大意：
成语接龙游戏。给定n个单词，每个单词前面先给一个权值，表示由这个单词找到下一个单词所需要花费的时间。问从第一个单词至少要花多少时间才能找到最后一个单词。如果不能找到，输出-1
题目思路：
如果一个单词的最后一个字和另一个成语的第一个字一样的话。那么就可以连一个有向边。就是求一个最短路。注意：题目中说成语至少三个字，别想当然地以为成语就是4个字的……开始没注意到，后来才改的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <stack> 7 #include <queue> 8 #include <map> 9 #include <set> 10 #include <vector> 11 #include <cmath> 12 #include <algorithm> 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 using namespace std; 16 typedef long long int LL; 17 const int MAXN = 0x3f3f3f3f; 18 const int MINN = -0x3f3f3f3f; 19 const double eps = 1e-9; 20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1}, 21 {1,1},{1,-1},{-1,-1}}; 22 const int MAX = 1000+10; 23 int dist[MAX], S[MAX], n, wei[MAX], edge[MAX][MAX]; 24 char start[MAX][10], end[MAX][10], ch[50]; 25 void Dijkstra(int u0) { 26 int i, j; 27 for (i = 1; i <= n; ++i) { 28 S[i] = 0; dist[i] = edge[u0][i]; 29 } 30 S[u0] = 1; dist[u0] = 0; 31 int u; 32 for (i = 1; i < n; ++i) { 33 int Min = MAXN; u = 1; 34 for (j = 1; j <= n; ++j) { 35 if (S[j] == 0 && dist[j] < Min) { 36 Min = dist[j]; u = j; 37 } 38 } 39 S[u] = 1; 40 for (j = 1; j <= n; ++j) { 41 if (S[j] == 0 && edge[u][j] != MAXN) { 42 int tmp = edge[u][j] + dist[u]; 43 if (tmp < dist[j]) dist[j] = tmp; 44 } 45 } 46 } 47 if (dist[n] == MAXN) printf("-1\n"); 48 else printf("%d\n", dist[n]); 49 } 50 int main(void){ 51 #ifndef ONLINE_JUDGE 52 freopen("zoj2750.in", "r", stdin); 53 #endif 54 int i, j, k; 55 while (~scanf("%d", &n) && n) { 56 for (i = 1; i <= n; ++i) { 57 scanf("%d%s", &wei[i], ch); 58 for (j = 0; j < 4; ++j) start[i][j] = ch[j]; 59 int len = strlen(ch); 60 for (j = 0, k = len-4; k < len; ++k, ++j) end[i][j] = ch[k]; 61 start[i][4] = '\0'; end[i][4] = '\0'; 62 } 63 for (i = 1; i <= n; ++i) { 64 for (j = 1; j <= n; ++j) { 65 if (i != j && strcmp(end[i], start[j]) == 0) { 66 edge[i][j] = wei[i]; 67 } else edge[i][j] = MAXN; 68 } 69 } 70 Dijkstra(1); 71 } 72 73 return 0; 74 }
这题……呵呵。不想说别的，我去年买了个表！
WA了很久关键是测试数据还都对，也怪自己，没有出一些比较有水平的数据。检测不出错误来。我不会告诉你原来错误出在，35行把dist[j]写成了edge[u][j]。真不知道自己写代码的时候，到底有没有过脑子！
本来思路很清晰，好不容易会做了，结果这么悲剧，唉，淡定。
还有就是，程序出错了，不能急，自己从头屡屡思路，看有没有出现代码错误，还有边界条件神马的。
这题关键在预处理，开始觉得比较麻烦，其实写出来就感觉一点儿也不麻烦，再说，麻烦的题目才能锻炼代码能力。
整天就是切题切题，切你妹啊！！到考试了傻B了，，还有，，知道为什么自己做题效率这么低么？就是因为做题的时候不认真，不细心，浪费很多时间。
其实今天这个错误，也反映出一个问题，就是，没有真正理解算法，只是按照记忆写的，敲错也不奇怪了。。如果你真正理解了这个算法的思想，就可以按照自己的思路去写，有自己的思考，就不会出现这个错误，即使出现敲错了的情况，也可以再查错的时候很快发现。
查错是一种超级重要的能力。
代码的准确度同样也是。
好吧，算法真的学得不如别人，人家都可以很快就过，我却纠结这么久。没什么可说的。敲得少，练得少，代码弱。
还有就是，以后出现这种当时怎么也查不出错的情况的时候，可以先放一下，等过了半天再重新看，重新思考，也许就可以很快发现错误了，因为很可能当时你已经没有耐心去查错了，很可能陷入了一种思维的误区和思维定式。可以先看别的，做下一道题目，这样也许就可以节约很多时间。
做题能够1A，真是一件不容易的事情。