毕业旅行省钱问题

在家自行维修一些小问题，比请专业人员更省钱。 #生活技巧# #节省生活成本# #家居省钱技巧# #家居用品购物攻略#

某实验室汇集了来自不同省份的研究僧。临近毕业，组中小袁提议进行一次毕业旅行，给大家的研究僧生涯留下一个美好的纪念。小李觉得非常不错，表示强烈支持后整天想着该怎么玩。一天，小李老师出差，闲来无事，便又开始胡思乱想，神游至行程问题：从福州出发，最后回到福州，如何在几个省会（南昌、南京、合肥、太原、郑州）之间旅行最省路费？遂写下此C++代码，交给计算机得解。记于此，便日后有用。

代码思路：将所有城市以及之间的旅途可看作一张全连接无向带权图，从某起点出发进行深度优先搜索，寻找权重最小环。

#include <vector>

#include<iostream>

#include<string>

using namespace std;

struct City//城市节点，记录名称以及是否被访问

{

bool visited;

string name;

City():visited(false),name("no name"){}

};

enum CityName{

FuZhou=0,

NanChang=1,

NanJing=2,

HeFei=3,

TaiYuan=4,

ZhengZhou=5,

TotCity=6,

};

const static int TravelPrice[TotCity][TotCity]={//各个城市之间的车票或者飞机票价格

{0,160,314,357,430,451},

{160,0,369,316,235,291},

{314,369,0,67,395,317},

{357,316,67,0,278,307},

{430,235,395,278,0,257},

{451,291,317,307,257,0}

};

const static string CityName_s[TotCity]={

"FuZhou","NanChang","NanJing","HeFei","TaiYuan","ZhengZhou"

};

class Solution {

public:

string SearchLowestPricePath(){

string path, optPath; //可能的路径以及最佳路径

int price=0, optPrice=INT_MAX; //可能的价格以及最佳价格

vector<City> ourCity(TotCity);

for(int i=0; i<TotCity; i++)

ourCity[i].name=CityName_s[i];

path="start";

Travel(ourCity, FuZhou, path, optPath, price, 5, optPrice);//5块乘地铁

return optPath;

}

void Travel(vector<City> visCity, int lastCity, string path, string& optPath, int Price, int curPrice, int& optPrice){

visCity[lastCity].visited=true;//上一城市已游玩

path=path+" -> "+CityName_s[lastCity];//路径历史

Price+=curPrice;

for(int i=0; i<TotCity; i++){

if(!visCity[i].visited)

break;

else if(i==TotCity-1){//递归基，所有城市都已访问，回福州

Price+=TravelPrice[lastCity][FuZhou];

path=path+" -> "+CityName_s[FuZhou]+" "+to_string(Price);

if(Price<optPrice){

optPrice=Price;

optPath=path;

}

return;

}

}

for(int i=1; i<TotCity; i++){//去下一个城市

if(visCity[i].visited)//去过的不去

continue;

Travel(visCity, i, path, optPath, Price, TravelPrice[lastCity][i], optPrice);

}

}

};

int main()

{

Solution c;

cout<<c.SearchLowestPricePath()<<endl;

system("pause");

return 0;

}

希望顺利毕业。

网址：毕业旅行省钱问题 https://www.yuejiaxmz.com/news/view/444662

相关内容

最省钱的毕业旅行攻略
外出旅行省钱的技巧有哪些？外出旅行省钱的技 – 手机爱问
湖南张家界苗寨旅游攻略五天超省钱毕业旅行必备，快看
去哪儿网：省钱旅行，不如去省钱的旅行
旅游省钱小技巧（旅游省钱）
如何在旅行中省钱（附：吃住行省钱攻略）
怎样旅行省钱呢想去多一点地方少一点钱 爱问知识人
旅游省钱秘籍，教你花最少的钱去旅行！（转）
一些旅行省钱技巧
旅途中怎样省钱，最全旅游省钱攻略

随便看看