Tom 是調皮的孩子，特別喜歡玩火，現在他手上有若干根長度分別爲 1 和sqrt(2) 的木棍，還有一張不能燃燒的平板，他把平板劃分成長度爲 1 的單元格，並標上座標。然後按以下規則把平板上的木棍組成一個連通圖：木棍的兩端必須放在單元格的頂點上。即長度爲 1 的木棍放在單元格的某一邊上，長度爲sqrt(2) 的木棍放在單元格的對角綫上。
Tom 的點火規則是，只能從木棍的兩端點火，而不能從木棍的中間點火。 如圖 ，不能在 A 點點火，但在 C 點或 B 點點火都是充許的。點火後，火會沿着木棍向前燃燒（每根都有自己的燃燒速度），並能點燃與它相接的其它木棍。
任務： 寫一程序計算從哪裏開始點火，使得燃燒的總時間最短，輸出最短時間。
Input Data
輸入文件第一行爲一個正整數 N ，表示組成圖形的木棍數目，後面共有 N 行，每行 5 個數： X1 Y1 X2 Y2 T , 其中（ X1 , Y1 ） 和（ X2 , Y2 ）分別表示木棍兩端的座標， T 表示木棍燃燒時間，是指從木棍的某一端點火燃燒到別一端，燃完所需的時間。
Output Data
輸出文件是一個保留 4 位小數的實數，表示所有木棍完全燃燒的最少時間。
約束
1 ≤n≤40
保證圖形是連通的，所有的木棍長度都是 1 或sqrt(2) ，沒有任何兩根木棍重合 .
-200≤ X1, Y1, X2, Y2 ≤200; 0≤ T ≤ 10^7 .
如果你的輸出結果與標準答案相差小於 0.001 ，則認爲你的結果正確。
樣例 1
fire.in
1
0 0 1 1 1
fire.out
1.0000
解釋：從任一端點火都行，燃燒時間都是 1
樣例 2
fire.in5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1
fire.out
3.2500
解釋：在 (0,0) 位置點火
木棍 1, 3 和 4 將被點燃，燃燒 0.5 分鐘後，木棍 2 將被從中間點燃向兩端燃燒，再過 0.5 分鐘，木棍 1, 3, 4 將被完全燃燒，木棍 5 將被點燃並在 1 分鐘後燃燒完 ( 比木棍 2 早燃完 ) 。
木棍 2 從中間向兩端燃燒 0.5 分鐘以後，變成兩小段，每段的燃燒時間是 4.5 分鐘。但因爲此時兩小段木棍的另一端也同時被點燃，燃燒速度變成原來的兩倍，還需 2.25 分鐘的燃燒時間， 所以總時間： 1 + 2 . 25 = 3 . 25
樣例 3
fire.in3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
fire.out
35.0000
解釋：在 (1,2) 位置點火， 木棍 (1 1, 1 2) 和 (1 2, 2 2) 將燃燒 10 分鐘。 . 最後一根木棍在 10 分鐘後從兩端被點燃，燃燒時間爲 25 分鐘。
【分析】
Floyd算法求最短路，只是構圖很困難罷了。
具體算法的PPT課件下載：http://zhuyifan.net84.net/ppt/fire.ppt
【我的代碼】
/*
*Problem: 燃燒木棍 fire
*Author: Yee-fan Zhu
*Date: Dec.01.2011
*Website: www.zyfworks.tk
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;
double max(double x,double y)
{
if(y>x)
x=y;
return x;
}
class Wood
{
public:
double x1,x2;
double y1,y2;
double time;
}F[42];
class Point
{
public:
double x,y;
}P[1000];
Wood W[1000];
int D=0;
int M=0;
double Mat[1002][1002];
int Used[2000][2000];
const int add=500;
void init()
{
std::ios::sync_with_stdio(false);
scanf("%d\n",&N);
for (int i=-450;i<=1050;i++)
for (int j=-450;j<=1050;j++)
Used[i+add][j+add]=-1;
for (int i=1;i<=300;i++)
for (int j=1;j<=300;j++)
Mat[i][j]=10000000;
for (int i=1;i<=300;i++)
Mat[i][i]=0;
for (int i=1;i<=N;i++)
{
scanf("%lf %lf %lf %lf %lf\n",&F[i].x1,&F[i].y1,&F[i].x2,&F[i].y2,&F[i].time);
}
double x1,x2,y1,y2,t;
for (int i=1;i<=N;i++)
{
x1=F[i].x1,y1=F[i].y1;
x2=F[i].x2,y2=F[i].y2;
t=F[i].time;
int p1,p2;
p1=Used[int(x1*2)+add][int(y1*2)+add];
p2=Used[int(x2*2)+add][int(y2*2)+add];
if(p1==-1)
{
M++;
Used[int(x1*2)+add][int(y1*2)+add]=M;
P[M].x=x1,P[M].y=y1;
p1=M;
}
if(p2==-1)
{
M++;
Used[int(x2*2)+add][int(y2*2)+add]=M;
P[M].x=x2,P[M].y=y2;
p2=M;
}
Mat[p1][p2]=t;
Mat[p2][p1]=t;
bool flag=true;
if(F[i].x1-F[i].x2==0 || F[i].y1-F[i].y2==0)
{
D++;
W[D].x1=x1,W[D].y1=y1;
W[D].x2=x2,W[D].y2=y2;
W[D].time=t;
continue;
}
double x3,y3;
double x4,y4;
if((x1>x2 && y1>y2 )||(x1<x2 && y1<y2 ))
{
if(x1>x2 && y1>y2 )
{
x3=x1-1;
y3=y1;
x4=x1;
y4=y1-1;
}
if(x1<x2 && y1<y2)
{
x3=x1;
y3=y1+1;
x4=x1+1;
y4=y1;
}
}
else
{
if(x1<x2 && y1>y2)
{
x3=x1;
y3=y1-1;
x4=x1+1;
y4=y1;
}
if(x1>x2 && y1<y2)
{
x3=x1-1;
y3=y1;
x4=x1;
y4=y1+1;
}
}
for (int j=1;j<=N;j++)
{
if((F[j].x1==x3 && F[j].y1==y3 && F[j].x2==x4 &&F[j].y2==y4) || (F[j].x1==x4 && F[j].y1==y4 && F[j].x2==x3 &&F[j].y2==y3) )
{
double x5,y5;
x5=double((x1+x2)/double(2));
y5=double((y1+y2)/double(2));
int p3=Used[int(x5*2)+add][int(y5*2)+add];
if(p3==-1)
{
M++;
p3=M;
P[M].x=x5,P[M].y=y5;
Used[int(x5*2)+add][int(y5*2)+add]=M;
}
Mat[p3][p1]=t/(double(2)),Mat[p1][p3]=t/(double(2));
Mat[p2][p3]=t/(double(2)),Mat[p2][p3]=t/(double(2));
D++;
W[D].x1=x3,W[D].y1=y3;
W[D].x2=x5,W[D].y2=y5;
W[D].time=t/(double(2));
D++;
W[D].x1=x4,W[D].y1=y4;
W[D].x2=x5,W[D].y2=y5;
W[D].time=t/(double(2));
flag=false;
break;
}
}
if(flag)
{
D++;
W[D].x1=x1,W[D].y1=y1;
W[D].x2=x2,W[D].y2=y2;
W[D].time=t;
}
}
}
void Floyd()
{
double tmp;
for (int k=1;k<=M;k++)
{
for (int i=1;i<=M;i++)
{
for (int j=1;j<=M;j++)
{
tmp=Mat[i][k]+Mat[k][j];
if(tmp<Mat[i][j])
Mat[i][j]=tmp;
}
}
}
}
void work()
{
double tot=100000000;
for (int i=1;i<=M;i++)
{
double x,y;
x=P[i].x;
y=P[i].y;
int tmp;
tmp=int(x*2);
if(tmp%2!=0)
continue;
int p=Used[int(x*2)+add][int(y*2)+add];
double s=0;
for (int j=1;j<=M;j++)
s=max(s,Mat[p][j]);
double x1,x2;
double y1,y2;
int p1,p2;
double t1,t2;
double dif;
double need;
for (int j=1;j<=D;j++)
{
x1=W[j].x1,y1=W[j].y1;
x2=W[j].x2,y2=W[j].y2;
p1=Used[int(x1*2)+add][int(y1*2)+add];
p2=Used[int(x2*2)+add][int(y2*2)+add];
t1=Mat[p][p1];
t2=Mat[p][p2];
double mint=t2;
if(t1<mint)
mint=t1;
dif=max(t1-t2,t2-t1);
if(dif>=W[j].time)
continue;
need=(W[j].time-dif)/(double(2));
need=need+mint+dif;
if(need>s)
s=need;
}
if(s<tot)
tot=s;
}
printf("%.4lf",tot);
}
int main()
{
freopen("firez.in","r",stdin);
freopen("firez.out","w",stdout);
init();
Floyd();
work();
return 0;
}
