ZZULIOJ 1799: wrz的压岁钱【数学】

系统管理员 2022-08-18 10:59 138阅读 0赞

## 1799: wrz的压岁钱 ##

Time Limit: 1 Sec Memory Limit:  128 MB  
Submit: 394 Solved: 66  
  
[Submit][] [Status][] [Web Board][]

## Description ##

马上要过年了，电子信息wrz要去亲戚家拿压岁钱。

他的亲戚有三家，他有一辆谷鸽牌电动车，电量只能支持从自己家骑到任意一家亲戚家，然后电动车就会没电了，电动车会放在该亲戚家充电。

剩下的两家亲戚由电子信息wrz步行过去，之后再回来骑充满电的谷鸽牌电动车回家。

但是电子信息wrz比较懒，不喜欢走太多路，你能帮他算出最少要走多少路程吗？

## Input ##

第一行为数字T，表示有T（1<=T<=1000)组测试数据。

每组数据占一行，分别有三个整数x,y,z,代表三家中任意两家的路程。(1<=x,y,z<=10^9)

例如：三家亲戚分别为a，b，c，则三个数字分别为a到b的路程，b到c的路程，c到a的路程。

## Output ##

每个实例输出占一行：格式为Case \#x: y

x为第x个实例，y为电子信息wrz需要走的最短路程。

## Sample Input ##

1 2 3

4 5 6

7 8 9

## Sample Output ##

Case \#1: 6

Case \#2: 15

Case \#3: 24

## 解题思路 ##

考虑到最短路，三个点最少要两个点连成，还要回到出发点，所以直接两点相加乘二，再加上三点相加拍序，找出最小值。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    long long map[1000];
    long long map1[1000];
    bool cmp(long long a,long long b)
    {
    	return a<b;
    }
    int main()
    {
    	int T;
    	int an=0;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int i,j;
    		for(i=0;i<3;i++)
    		{
    			scanf("%lld",&map[i]);
    		}
    		int cnm=0;
    		for(i=0;i<3;i++)
    		{
    			for(j=i+1;j<3;j++)
    			{
    				map1[cnm++]=2*(map[i]+map[j]);	
    			}
    		}
    		map1[cnm++]=map[0]+map[1]+map[2];
    		sort(map1,map1+cnm,cmp);
    		printf("Case #%d: %lld\n",++an,map1[0]);
    	}
    	return 0;
    }

[Submit]: http://acm.zzuli.edu.cn/submitpage.php?id=1799
[Status]: http://acm.zzuli.edu.cn/problemstatus.php?id=1799
[Web Board]: http://acm.zzuli.edu.cn/bbs.php?pid=1799