最终的骨牌要么是关键点，要么是两个关键点中间的两个点。先求最短路，然后求出每条边上的骨牌完全倒下的时间。
以下是我的代码：
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(507);
const int kInf(0x7f7f7f7f);
int n,m,g[kMaxn][kMaxn];
int d[kMaxn];
void Dijkstra()
{
bool visited[kMaxn]={false};
for(int i=1;i<=n;i++)
d[i]=(i==1?0:kInf);
for(int i=1;i<=n;i++)
{
int p(-1);
for(int j=1;j<=n;j++)
if(!visited[j] && (p<0 || d[p]>d[j]))
p=j;
visited[p]=true;
for(int j=1;j<=n;j++)
if(!visited[j] && g[p][j]<kInf && d[j]>d[p]+g[p][j])
d[j]=d[p]+g[p][j];
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T(0);
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=(i==j?0:kInf);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v]=g[v][u]=w;
}
Dijkstra();
int ans1(-kInf),key(1);
for(int i=1;i<=n;i++)
if(ans1<d[i])
{
ans1=d[i];
key=i;
}
double ans2(-kInf);
int start,end;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]<kInf && ans2<(d[i]+d[j]+g[i][j])/2.0)
{
ans2=(d[i]+d[j]+g[i][j])/2.0;
start=i;
end=j;
}
T++;
printf("System #%d\n",T);
if(ans1>=ans2)
printf("The last domino falls after %.1f seconds, at key domino %d.\n\n",(double)ans1,key);
else
printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n",ans2,start,end);
}
return 0;
}
posted on 2011-07-31 09:32
lee1r 阅读(334)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论