就是一道脑筋急转弯,思路挺有意思的,记一下。
因为是双向道路,而且两边都要走一遍,因此这就保证了每个点的入度与出度都是相等的,加上起点可以到任意其他点,于是整个图保证是欧拉回路,又因为每一条边都要走过,故按照欧拉回路走一定是最优解。
代码:
#include<bits/stdc++.h>
using namespace std;
double f(double x){
return x*x;
}
int main(){
double res=0;
double x1, y1, x2, y2;
cin>>x1>>y1;
while(cin>>x1>>y1>>x2>>y2){
res+=sqrt(f(x1-x2)+f(y1-y2))*2;
}
int minu=round(res/1000/20*60);
int hour=minu/60; minu%=60;
printf("%d:%02d\n", hour, minu);
return 0;
}