`
linest
  • 浏览: 149597 次
  • 性别: Icon_minigender_1
  • 来自: 内蒙古
社区版块
存档分类
最新评论

ZOJ-2433 修路

    博客分类:
  • acm
 
阅读更多
2433:一条高速路沿线有很多城市,间距不等,但高速路是单行的。现在要修两条反向的路使车辆可以返回任意村子。求使总路程最小的两条路地起点和终点。同时要求每个城市最多只能有一条路。

   ----
A B C D E      这种不行,过了D就回不到前面去了。
            ----

分析后发现,两条路必须有重叠部分,而且第一个城市和最后一个城市必须包括在内。为了总路程最短,重叠部分为两个相邻城市的间隔

-------
A B C D E      总路程为全长加重叠。问题转化为寻找相邻最近的两城市。
   -----------


#include<stdio.h>
#include<iostream>
using namespace std;

int main()
{	
	int N;
	int S1;
	int E1=1;
	int S2;
	int E2;
	int num;  //city number
	int prev;  //previous city
	int curr;  //current city
	int min;   //minimum dis between two city
	int tmp;
	int total;   //dis between first and last

	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>num;
		S2=num;
		for(int k=1;k<num;k++)
		{
			cin>>curr;
			if(k==1)
			{
				prev=curr;
			}
			else if(k==2)
			{
				min=curr-prev;
				E2=k;
				S1=k+1;
				prev=curr;
			}
			else if(k==num-1)
			{
				total=curr;
			}
			else 
			{
				tmp=curr-prev;
				if(tmp<min)
				{
					min=tmp;
					E2=k;
					S1=k+1;
				}
				prev=curr;
			}
		}

		if(num<4)
		{
			cout<<0<<endl;
		}
		else
		{
			//total length
			cout<<total+min<<endl;
			cout<<S1<<" "<<E1<<" "<<S2<<" "<<E2<<endl;
		}
		
		
		if(i!=N-1)
			cout<<endl;

	}


}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics