poj1135&&zoj1298 Domino Effect ——最短路入门题_Dijkstra算法

May 5, 2013
POJ Graph

题目链接：http://poj.org/problem?id=1135　　http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=298 题目大意：　　有n个多米诺骨牌，有m条边，推倒第1张牌，以这个点为端点边上的的牌同时倒，问最后倒下的那张牌是哪张，并且求出时间。如果正好是端点上的牌，输出端点序号，否则需要输出这个点在哪两个端点之间。题目思路：　　假设骨牌倒下的速度是1.这样就可以用距离表征时间了。　　如果最后倒下的牌正好是端点处的。那么就很好理解了，就是求所有点到这个点的最短路的最大值。设为Max1 　　如果最后倒下的是某两个端点之间的牌。那么就要认真想想了。比如是A点和B点之间的。可以先分别求出到A点的时间，和到B点的时间。然后再加上A和B之间的距离。所得的和就是从起点1到达最后终点的时间的两倍！为什么捏？可以这么思考：两个人，速度都是1，从起点开始，以同样的速度行走，然后在同一时刻到达同一点，那么他们所花的时间的和就是从起点到终点的距离的两倍嘛。不管他们分别到达A点和B点的先后顺序，总之，他们最后的效果都是相遇了！对于每一条边，都求出对应的时间。得到最大值，设为Max2 　　如果Max2 > Max1 说明什么捏？说明了：两个人仅仅到达某些端点，并不能相遇有木有！还需要再走一段路程，在某两个端点之间的某处相遇！并且，这两个端点就是当Max2最大的时候的两个端点。　　如果两者相等或者Max1 > Max2 说明什么捏？其实貌似不能大于……因为，Max1就是起点到达所有点的最短距离的最大值嘛，而Max2是每条边上时间的最大值，然后可以发现，除了第一种情况，每条边上时间的最大值其实就是到达这条边的其中一个端点的时间的最大值……所以呢，Max1不能大于Max2.出去第一种情况狂，只能等于。　　然后这道题目还有一个需要注意的地方，就是，当只有一张骨牌的时候，输出0.0……这种情况，，好吧，真不知道比赛的时候我怎么能想得出来……


#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 = 500+10;
int dist[MAX], S[MAX], edge[MAX][MAX], n, m;
void dijkstra(int v0) {
  int i, j;
  for (i = 1; i <= n; ++i) {
    S[i] = 0; dist[i] = edge[v0][i];
  }
  S[v0] = 1;
  for (i = 1; i < n; ++i) {
    int Min = MAXN, u;
    for (j = 1; j <= n; ++j) {
      if (S[j] == 0 && Min > dist[j]) {
        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;
        }
      }
    }
  }
  double Max1 = MINN*1.0, Max2 = MINN * 1.0;
  int index, index1, index2;
  for (i = 2; i <= n; ++i) 
    if (Max1 < dist[i]) {Max1 = 1.0 * dist[i]; index = i;}
  for (i = 1; i <= n; ++i) {
    for (j = i+1; j <= n; ++j) {
      if (edge[i][j] != MAXN) {
        double tmp = (dist[i] + dist[j] + edge[i][j]) / 2.0;
        if (tmp > Max2) {
          Max2 = tmp; index1 = i; index2 = j;
        }
      }
    }
  }
  if (n == 1) {Max1 = 0.0; index = 1;}
  if (Max2 > Max1) {
    printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n", Max2, index1, index2);
  }
  else {
    printf("The last domino falls after %.1f seconds, at key domino %d.\n", Max1, index);
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1135.in", "r", stdin);
#endif
  int i, j, u, w, v, t = 1;
  while (~scanf("%d%d", &n, &m) && (n||m)) {
    printf("System #%d\n", t); t++;
    memset(edge, 0, sizeof(edge));
    for (i = 1; i <= m; ++i) {
      scanf("%d%d%d", &u, &v, &w);
      edge[v][u] = edge[u][v] = w;
    }
    for (i = 1; i <= n; ++i) {
      for (j = i; j <= n; ++j) {
        if (j == i) edge[i][j] = 0;
        else if (edge[i][j] == 0) edge[i][j] = edge[j][i] = MAXN;
      }
    }
    dijkstra(1);
    printf("\n");
  }

  return 0;
}

　　开始WA了一次，原因是输出的语句写错了……当初我还特意检查了一下，可能是因为当时gvim的窗口开得太小了，没看清楚……后来WA就是那个只有1张骨牌的特例…… 　　唉，承认自己不聪明，人家立马就过了这题，赶脚丝毫没有难度。我却想很久……唉，只有靠自己的努力吧，也许是因为刚开始学最短路，想不明白，也许是思维不灵活，不能把一个复杂的问题，转化成一个简单的问题，分析问题的方法很重要，如何分析某个问题，是自己要认真体会的。比如说这道题目，其实想明白了也就那么回事儿，可是当初为什么自己就觉得那么难呢？不认真想想，就屁颠屁颠地问别人……呵呵　　这是病，得治。　　唉，后来发现一个问题，其实，不用考虑骨牌数目为1的情况，你只需要在49行循环变量从1开始就可以了么，然后就可以把61行的特例判断去掉了。还是考虑不周全啊，当初为什么我把循环变量搞成从2开始？？想不通……像这种边界条件，写代码的时候就要考虑到！不能写完再检查，那个时候通常就检查不出来了。。

Read more