問題描述

隨著白天越來越短夜晚越來越長，我們不得不考慮鏟雪問題了。整個城市所有的道路都是雙向一個車道，因為城市預算的削減，整個城市只有1輛鏟雪車。鏟雪車只能把它開過的地方（車道）的雪鏟干凈，無論哪兒有雪，鏟雪車都得從停放的地方出發(fā)，游歷整個城市的街道?，F(xiàn)在的問題是：最少要花多少時間去鏟掉所有道路上的雪呢？

輸入文件（snow.in）

輸入數(shù)據(jù)的第1行表示鏟雪車的停放坐標（x,y），x，y為整數(shù)，單位為米。下面最多有100行，每行給出了一條街道的起點坐標和終點坐標，所有街道都是筆直的，且都是雙向一個車道。鏟雪車可以在任意交叉口、或任何街道的末尾任意轉向，包括轉U型彎。鏟雪車鏟雪時前進速度為20 km/h，不鏟雪時前進速度為50 km/h。

保證：鏟雪車從起點一定可以到達任何街道。

輸入文件（snow.out）

鏟掉所有街道上的雪并且返回出發(fā)點的最短時間，精確到分種。

樣例輸入

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

樣例輸出

3:55（但我的程序答案是3.54，用了很多增精度的辦法都沒用）

解題報告

這題目暗示了每個情況都是一個歐拉回路，所以直接根據(jù)歐拉圖的特點求出最終答案

#include<iostream>
#include<fstream>
#include<cmath>

using namespace std;

int tot,first,begin;//tot為總時間,（first，begin）為起點坐標，其實沒用 
int a,b,c,d;//每條路的起點坐標和終點坐標 
int hour,second;//輸出的時間 

int main(){
    freopen("snow.in","r",stdin);
    freopen("snow.out","w",stdout);//重定向文件 
    cin>>first>>begin;//讀入起點 
    while(cin>>a>>b>>c>>d){
        tot+=sqrt(pow(a-c,2)+pow(b-d,2));
    }tot=tot*2/1000;//算出要走的路的總長，即所有路道長度之和*2 
    tot=tot*3;//算出所用的總時間（單位為分鐘）
    hour=tot/60;//算出時間（小時）
    second=tot-hour*60;//算出時間（分鐘） 
    cout<<hour<<":"<<second<<endl;//輸出 
    return 0;
}