The clock shows 11:30 PM. The sports programmers of the institute of maths and computer science have just finished their training. The exhausted students gloomily leave their computers. But there’s
something that cheers them up: Misha, the kind coach is ready to give all of them a lift home in his brand new car. Fortunately, there are no traffic jams on the road. Unfortunately, all students live in different districts. As Misha is a programmer, he highlighted
and indexed five key points on the map of Yekaterinburg: the practice room (1), Kirill’s home (2), Ilya’s home (3), Pasha’s and Oleg’s home (4; they live close to each other) and his own home (5). Now he has to find the optimal path. The path should start
at point 1, end at point 5 and have minimum length. Moreover, Ilya doesn’t want to be the last student to get home, so point 3 can’t be fourth in the path.
Input
The input contains a table of distances between the key points. It has five rows and five columns. The number in thei’th row and thej’th column (1 ≤i,j≤ 5) is
a distance between pointsiandj. All distances are non-negative integers not exceeding 10000. It is guaranteed that the distance from any point to itself equals 0, and for any two points, the distance between them is the same in both directions.
It is also guaranteed that the distance between any two points doesn’t exceed the total distance between them through another point.
Output
Output two lines. The first line should contain the length of the optimal path. The second line should contain five space-separated integers that are the numbers of the points in the order Misha should
visit them. If the problem has several optimal solutions, you may output any of them.
Sample
input
output
0 2600 3800 2600 2500
2600 0 5300 3900 4400
3800 5300 0 1900 4500
2600 3900 1900 0 3700
2500 4400 4500 3700 0
|
13500
1 2 3 4 5
|
摆明的一个TSP问题,但是解决TSP问题的效率是相当低的。
不过这里的点数很少,而且有一个条件限制。
所以最后剩下的可选择的路径就很少了。于是这里我使用了暴力法,可以很轻松地通过。
技巧就是:预先产生了路径,那么速度就快了。
#include <vector>
#include <iostream>
using namespace std;
static const int NUM_OF_MEN = 5;
void TaxiforProgrammers2005()
{
vector<vector<int> > mat(NUM_OF_MEN, vector<int>(NUM_OF_MEN));
for (int i = 0; i < NUM_OF_MEN; i++)
{
for (int j = 0; j < NUM_OF_MEN; j++)
{
cin>>mat[i][j];
}
}
int routes[4][5] = { {1,2,3,4,5}, {1,3,2,4,5}, {1,3,4,2,5}, {1,4,3,2,5} };
int ans = 50000, rou = -1;
for (int i = 0; i < 4; i++)
{
int tmp = 0;
for (int j = 1; j < 5; j++)
{
tmp += mat[routes[i][j-1]-1][routes[i][j]-1];
}
if (tmp < ans)
{
ans = tmp;
rou = i;
}
}
cout<<ans<<endl;
for (int i = 0; i < 5; i++)
{
cout<<routes[rou][i]<<' ';
}
}
分享到:
相关推荐
《Data Structures For Game Programmers 2003》是一本专为游戏程序员设计的数据结构教程。数据结构是编程的基础,特别是在游戏开发中,高效的、合适的数据结构选择对于优化性能、提高代码可读性和降低复杂性至关...
《Wrox.SQL.Functions.Programmers.Reference.Apr.2005》这本书的PDF版本是数据库开发者和管理员的重要参考资料。Wrox出版社以其深入浅出的技术图书而闻名,此书也不例外,它详细介绍了SQL语言中的各种函数及其在...
《Prentice.Hall.Java.for.Programmers.2nd.Edition》是Deitel®开发者系列中的一个重要的编程资源,由Paul Deitel和Harvey Deitel共同撰写。这本书专注于Java编程语言,为读者提供了深入且全面的Java知识体系。下面...
《游戏程序员的数学与物理基础》是一本专为游戏开发人员设计的教材,它深入浅出地介绍了在游戏编程中不可或缺的数学和物理知识。在游戏开发中,无论是2D还是3D,数学和物理都是核心技能,它们帮助开发者创建真实、...
Packt.Raspberry.Pi.3.Cookbook.for.Python.Programmers.3rd.Edition.2018
《Wrox.Visual.Basic.2005.Programmers.Reference》是一本专为Visual Basic 2005开发者设计的详尽编程指南。这本书由Wrox出版社出版,旨在帮助程序员深入理解和应用VB2005的强大功能。作为一本英文PDF文档,它涵盖了...
Android.A.Programmers.Guide.Jul.2008-336页的电子书-美金$30.39 Android.A.Programmers.Guide.Jul.2008-336页的电子书-美金$30.39 Android.A.Programmers.Guide.Jul.2008-336页的电子书-美金$30.39 Android.A....
Prentice Hall - Linux.for.Programmers.and.Users.Feb.2006.chm
《Prentice.Hall.iPhone.for.Programmers.Oct.2009》这本书,作为针对程序员的iPhone开发指南,深入浅出地介绍了如何利用苹果的iOS SDK进行应用程序开发。这本压缩包中的PDF文件,很可能是该书的电子版,为开发者...
Java.For.S.390.and.AS.400.COBOL.Programmers.chm
### 关于《TCPIP.Sockets.in.Java.Practical.Guide.for.Programmers.2nd.Edition》的知识点解析 #### 一、书籍概述 本书名为《TCP/IP Sockets in Java: Practical Guide for Programmers, Second Edition》,是由...
Written for programmers with a background in high-level language programming, C# 6 for Programmers applies the Deitel signature live-code approach to teaching programming and explores Microsoft’s C# ...
《Packt.Raspberry.Pi.3.Projects.for.Java.Programmers.2017》这本书是专为Java程序员设计的一份指南,旨在利用Raspberry Pi 3这一强大的微型计算机平台进行项目开发。Raspberry Pi 3是一款受欢迎的开源硬件,常...
标题"AJAX.Rich.Internet.Applications.and.Web.Development.for.Programmers."揭示了本书的主题,主要关注的是使用AJAX(Asynchronous JavaScript and XML)技术来构建富互联网应用程序(Rich Internet ...
Unlike other books about R, written from the perspective of statistics, R for Programmers: Mastering the Tools is written from the perspective of programmers, providing a channel for programmers with ...
《Prentice Hall Java 9 for Programmers 4th Edition》是2017年发布的一本关于Java编程的权威教材,专为初学者和有经验的程序员设计。这本书深入浅出地介绍了Java 9这一版本的新特性和编程概念,旨在帮助读者掌握...
《游戏程序员的数学与物理基础》是一本专为游戏开发人员设计的入门级教程,旨在帮助初学者理解和应用数学和物理学的基本概念。2004年出版的这本书,至今仍具有很高的参考价值,因为数学和物理学是游戏编程的核心,...
《MIPS32 and MIPS64 Architecture For Programmers Volume I, II, III》是一套针对MIPS架构的程序员指南,涵盖了MIPS32和MIPS64两种指令集体系结构的详细信息。这套资料旨在帮助程序员深入理解MIPS处理器的工作原理...