题意描述：求出多米诺骨牌中从开始到最后那一块骨牌倒下所花费的时间。
解题思路：先用Dijkstra算法求出每一个关键点倒下时花的时间，然后判断最后一块骨牌倒下的位置，以确定其倒下的时间。我们知道最后一块骨牌要么就是关键点，要么在两个关键点之间。如果是在关键点之间的情况，假设这两个关键点的时间为t1和题t2，两点之间的边长为t3，则最后一块骨牌倒下所花时间为(t1+t2+t3)/2。
以下是本题代码：
（渐渐发现，做题不仅仅是比着书上已有的代码抄一遍那么简单）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define LEN 510
#define MAX INT_MAX
int mp[LEN][LEN];
int main()
{
int i, j;
int n, m;
int a, b, l;
int count = 1;
scanf("%d%d", &n, &m);
while(m + n != 0)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &l);
mp[a][b] = mp[b][a] = l;
}
int s[LEN] = {0};
int cost[LEN];
int cost1[LEN];
s[1] = 1;
for(i = 1; i <= n; i++)
if(mp[1][i] != 0)
cost[i] = mp[1][i];
else
cost[i] = MAX;
cost[1] = 0;
int t = 1;
for(j = 1; j <= n - 1; j++)
{
t = 1;
int min = MAX;
for(i = 1; i <= n; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= n; i++)
if(s[i] == 0 && mp[t][i] != 0 && mp[t][i] + cost[t] < cost[i])
cost[i] = mp[t][i] + cost[t];
}
int gard = 1;
double max = -MAX;
int p0;
for(i = 1; i <= n; i++)
if(max < cost[i])
{
max = cost[i];
p0 = i;
}
int p1 = 1;
int p2 = 1;
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
{
double x1 = 1.0 * (cost[i] + cost[j] + mp[i][j]) / 2;
if(mp[i][j] != 0 && x1 > max)
{
gard = 0;
max = x1;
p1 = i;
p2 = j;
}
}
if(count++ != 1)
putchar(10);
printf("System #%d\n", count - 1);
if(gard == 1)
{
printf("The last domino falls after %.1lf seconds, at key domino %d.\n", max, p0);
}
else
{
if(p1 > p2)
{
int t1 = p1;
p1 = p2;
p2 = t1;
}
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n", max, p1, p2);
}
scanf("%d%d", &n, &m);
}
//system("pause");
}
posted on 2012-08-09 20:04
小鼠标 阅读(208)
评论(0) 编辑 收藏 引用 所属分类:
图论