zoj2750 Idiomatic Phrases Game ——最短路入门题_Dijkstra算法

May 5, 2013
zoj Graph

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1750 题目大意：　　成语接龙游戏。给定n个单词，每个单词前面先给一个权值，表示由这个单词找到下一个单词所需要花费的时间。问从第一个单词至少要花多少时间才能找到最后一个单词。如果不能找到，输出-1 题目思路：　　如果一个单词的最后一个字和另一个成语的第一个字一样的话。那么就可以连一个有向边。就是求一个最短路。注意：题目中说成语至少三个字，别想当然地以为成语就是4个字的……开始没注意到，后来才改的。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f; 
const int  MINN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 1000+10;
int dist[MAX], S[MAX], n, wei[MAX], edge[MAX][MAX];
char start[MAX][10], end[MAX][10], ch[50];
void Dijkstra(int u0) {
  int i, j;
  for (i = 1; i <= n; ++i) {
    S[i] = 0; dist[i] = edge[u0][i];
  }
  S[u0] = 1; dist[u0] = 0;
  int u;
  for (i = 1; i < n; ++i) {
    int Min = MAXN; u = 1;
    for (j = 1; j <= n; ++j) {
      if (S[j] == 0 && dist[j] < Min) {
        Min = dist[j]; u = j;
      }
    }
    S[u] = 1;
    for (j = 1; j <= n; ++j) {
      if (S[j] == 0 && edge[u][j] != MAXN) {
        int tmp = edge[u][j] + dist[u];
        if (tmp < dist[j]) dist[j] = tmp;
      }
    }
  }
  if (dist[n] == MAXN) printf("-1\n");
  else printf("%d\n", dist[n]);
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj2750.in", "r", stdin);
#endif
  int i, j, k;
  while (~scanf("%d", &n) && n) {
    for (i = 1; i <= n; ++i) {
      scanf("%d%s", &wei[i], ch);
      for (j = 0; j < 4; ++j) start[i][j] = ch[j];
      int len = strlen(ch);
      for (j = 0, k = len-4; k < len; ++k, ++j) end[i][j] = ch[k];
      start[i][4] = '\0'; end[i][4] = '\0';
    }
    for (i = 1; i <= n; ++i) {
      for (j = 1; j <= n; ++j) {
        if (i != j && strcmp(end[i], start[j]) == 0) {
          edge[i][j] = wei[i];
        } else edge[i][j] = MAXN;
      }
    }
    Dijkstra(1);
  }

  return 0;
}

　　这题……呵呵。不想说别的，我去年买了个表！　　WA了很久关键是测试数据还都对，也怪自己，没有出一些比较有水平的数据。检测不出错误来。我不会告诉你原来错误出在，35行把dist[j]写成了edge[u][j]。真不知道自己写代码的时候，到底有没有过脑子！　　本来思路很清晰，好不容易会做了，结果这么悲剧，唉，淡定。　　还有就是，程序出错了，不能急，自己从头屡屡思路，看有没有出现代码错误，还有边界条件神马的。　　这题关键在预处理，开始觉得比较麻烦，其实写出来就感觉一点儿也不麻烦，再说，麻烦的题目才能锻炼代码能力。　　整天就是切题切题，切你妹啊！！到考试了傻B了，，还有，，知道为什么自己做题效率这么低么？就是因为做题的时候不认真，不细心，浪费很多时间。　　其实今天这个错误，也反映出一个问题，就是，没有真正理解算法，只是按照记忆写的，敲错也不奇怪了。。如果你真正理解了这个算法的思想，就可以按照自己的思路去写，有自己的思考，就不会出现这个错误，即使出现敲错了的情况，也可以再查错的时候很快发现。　　查错是一种超级重要的能力。　　代码的准确度同样也是。　　好吧，算法真的学得不如别人，人家都可以很快就过，我却纠结这么久。没什么可说的。敲得少，练得少，代码弱。　　还有就是，以后出现这种当时怎么也查不出错的情况的时候，可以先放一下，等过了半天再重新看，重新思考，也许就可以很快发现错误了，因为很可能当时你已经没有耐心去查错了，很可能陷入了一种思维的误区和思维定式。可以先看别的，做下一道题目，这样也许就可以节约很多时间。　　做题能够1A，真是一件不容易的事情。

Read more