学步园

题意：（看了半天没整明白）
有一个多米诺骨牌的游戏，我们知道有关键骨牌和普通骨牌，将关键骨牌推倒之后，整个骨牌阵就会倒下，推动其他的关键骨牌，其中推倒关键骨牌A使的关键骨牌B也倒，需要一定的时间，所以本题要求求出最后一个倒的骨牌的位置，及其时间...每个骨牌阵都由关键骨牌1推起

思路：对于倒的是关键骨牌我们可以通过Dijkstra来实现，而对于在中间倒的我们注意到一个现象——它所用的时间必然是这一行的两个关键骨牌到1骨牌的最短时间加上这一行的时间再除以2！！！用Dijkstra求出1点到其他点的最短时间，从中选个最大的MAX
然后求每行中间的，再求出最大的MAXJ然后比较MAXI和MAXJ的大小。

//   
1176K   
0MS
#include <stdio.h>
#include <string.h>
const int inf = 0x3f3f3f3f;
#define M 505

int mat[M][M];
int n;
void dij (int src)
{
    double
dis[M];
    int
mark[M],loc[2];
    int
k,i,j;
    for (i = 1;
i <= n; i ++)
    {
       
dis[i] = mat[src][i];
       
mark[i] = 0;
    }
    dis[src] =
0;
    mark[src] =
1;
    int m = n -
1;
    while (m
--)
    {
       
int min = inf;
       
for (i = 1; i <= n; i ++)
           
if (!mark[i]&&dis[i]
< min)
           
{
               
k = i;
               
min = dis[i];
           
}
       
mark[k] = 1;
       
for (i = 1; i <= n; i ++)
           
if (!mark[i] && dis[i]
> dis[k] + mat[k][i])
               
dis[i] = dis[k] + mat[k][i];

    }
    double max =
0;
    for (i = 2;
i <= n; i ++)
       
if (dis[i] > max)
       
{
           
k = i;
           
max = dis[i];
       
}
    double maxj
= 0;
    for (i = 1;i
<= n;i ++)
       
for (j = i+1;j <= n;j ++)
       
{