1.x的旅行

  (travel.pas/c/cpp)

【问题描述】

小x大学毕业后,进入了某个公司做了高层管理,他每年的任务就是检查这个公司在全国各地N个分公司的各种状况,每个公司都要检查一遍,且只能检查一遍,也就是说这N个地方只能也必须去一次。

当然,小x每年可以选择从任意一个城市开始,任意一个城市结束。

现在给出这N个公司所在地任意两个地点飞机票的价格,现在小x为了给公司省下交通费,需要设计一个程序,来计算一下如何花费最低能够完成任务。

作为一名有过信息学竞赛经历的有志青年,小x给自己的路线又规定了一个约束条件:如果要访问编号为K的城市,那么编号比K小的所有城市或者在访问K之前访问,或者在访问K之后访问。这个条件也必须遵守。

比如:如果有3个城市:2 1 3和 3 1 2 的顺序都是合法的,但是 1 3 2的顺序就是非法的,因为比3小的1在3之前,2在3之后,和小x的要求冲突。

【输入】

第一行:一个整数N。

接下来N行,每行N个整数。第i行第j列的值a[i][j]表示第i个城市到第j个城市飞机票的价格。保证这N个整数在[0..1000]之间。

【输出】

一个整数,表示满足要求的最小花费。

【输入输出样例1】

travel.in

travel.out

3

0 5 2

5 0 4

2 4 0

7

【输入输出样例2】

travel.in

travel.out

4

0 15 7 8

15 0 16 9

7 16 0 12

8 9 12 0

31

【样例解释】顺序为3, 1, 2, 4 或者 4, 2, 1, 3.

【数据范围】

30% 数据保证N<=10

50% 数据保证 N<=20

100% 数据保证 N<=1500

思路:

第一反应是dfs,但是如何判断是否符合题意呢?(反正我不会)。

仔细想想,点1不在中间,就在对头或队尾。那我们从1枚举到n分别放在上一次l,r的两边不就行了。

代码也不长。

Here is it;

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<ctime>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
int n,a[][];
int f[][];
int ans=maxn; int dfs(int l,int r)
{
if(f[l][r]) return f[l][r];
int next=max(l,r)+;
if(next==n+)
{
return ;
}
return f[l][r]=min(a[next][l]+dfs(next,r),a[r][next]+dfs(l,next));
} int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
{
dfs(,);
}
cout<<f[][]<<endl;
return ;
}
05-06 04:52