noip模拟题收费站（cost）C/C++代码在某个遥远的国家里，有n个城市。编号为1，2，3，……，n，并有m条双向的公路。每条公路连接着两个城市。开车每经过一个城市，都会被收取一定的费用

Question

noip模拟题 收费站（cost）C/C++代码
在某个遥远的国家里，有n个城市。编号为1，2，3，……，n，并有m条双向的公路。每条公路连接着两个城市。开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中。
小红现在要开车从城市u到城市v(1<=u，v<=n)。她的车最多可以装下s升的汽油。在出发时，车的油箱是满的，在路上不加油。
所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。
【输入格式】
第一行5个正整数，n，m，u，v，s。分别表示有n个城市，m条公路，从城市u到城市v，车的油箱的容量为s升。
接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。
再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，需要用ci升汽油。
【输出格式】
仅一个整数，表示小红交费最多的一次的最小值。
如果她无法到达城市v，输出-1。
【输入样例】
4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
【输出样例】
8
【数据规模】
对于100%的数据，满足n≤10000，m≤50000，s≤10^9，满足ci≤10^9，fi≤10^9，可能有两条边连接着相同的城市。

Answer 1

// StationCost.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
#include
#include
//记录每一步的选择。
struct SearchStep
{
int city;
int road;
int s;
SearchStep* next;
SearchStep* pre;
};
struct Road
{
int startc;
int endc;
int ci;
};
int FindNextCity(SearchStep* as,Road* ar,int n)
{
//查找线路是否有一端符合当前城市
int icity;
SearchStep* ps;
if (ar->startc == n)
icity = ar->endc ;
else if (ar->endc == n)
icity = ar->startc ;
else
return 0;
//查找线路是否已经过另一端城市
ps = as;
while (ps != NULL)
{
if (ps->city == icity)
return 0;
ps = ps->next ;
}
return icity;
}
int DoSearch(SearchStep* as,int aa,Road* ar,int* ac,int* ap,int ad)
{
//as 搜寻的路径；
//aa 公路数，ar 公路信息
//ac 最低的最高线路途经城市费用
//ap 城市收费信息
//ad 目标城市
int m,nextcity,nexts,ipay,imax;
SearchStep *ps,*pp;
ps = as;
if (ps->city == ad)
{
//查找所经过的路径，设置最大缴费值，比较缴费值和起讫城市的收费值，如果和其中之一相等，则直接返回
pp = ps;
while (pp != NULL)
{
ipay = *(ap + pp->city -1);
if (imax < ipay)
imax = ipay;
pp = pp->pre ;
}
*ac = imax;
if ((imax == *(ap + as->city -1)) || (imax == *(ap + ps->city -1)))
return 1;
else
{
if (ps->pre != NULL)
{
ps = ps->pre ;
ps ->next = NULL;
}
return 0;
}
}
m = ps->road;
while (m < aa)
{
nextcity = FindNextCity(as,ar + m,ps->city);
if (nextcity > 0)
{
//执行到下一步
if (*ac > 0)
if (*(ap + nextcity -1) > *ac)
{
//如果所到城市的费用大于已有线路最大费用，跳过
m++;
continue;
}
if (ps->s - (ar + m)->ci > 0)
{
ps->next = new SearchStep;
ps->road = m;
ps = ps->next;
ps->next =NULL;
ps->pre =as;
ps->city = nextcity;
ps->road = 0;
ps->s = as->s - (ar + m)->ci;
nexts = DoSearch(ps,aa,ar,ac,ap,ad);
if (nexts == 1) return nexts;
}
}
m++;
}
if (ps->pre != NULL)
{
ps = ps->pre ;
ps ->next = NULL;
}
return 0;
}
int main(int argc, char* argv[])
{
//第一步，录入城市数量，线路数量，出发城市，目标城市，汽车油箱容量
int ccount,rcount,startc,endc,vehs,imaxcost;
int inputright;
inputright = 0;
while (inputright == 0)
{
cout << "请输入城市数量，线路数量，出发城市，目标城市，汽车油箱容量\n";
cin >> ccount >> rcount >> startc >> endc >> vehs;
if (startc > ccount || endc > ccount)
cout << "出发城市或目标城市不能大于城市数，请重新输入！";
else if (ccount > 10000)
cout << "城市数量不能大于10000，请重新输入！";
else if (rcount > 50000)
cout << "线路数量不能大于50000，请重新输入！";
else
inputright ++;
}
//初始化城市收费，线路信息
int *Pcity = new int [ccount];
Road *Proad = new Road [rcount];
int i,num1,num2,num3;
srand((unsigned)time(NULL));
for (i = 0;i {
num1 = rand()%10000 + 1;
*(Pcity + i) = num1;
}
for (i = 0; i {
num1 = rand()%ccount + 1;
num2 = rand()%ccount + 1;
if (num1 == num2)
{
num2 = (num1 + 1) % ccount + 1;
}
(Proad + i)->startc = num1;
(Proad + i)->endc = num2;
num3 = rand()%10000 + 1;
(Proad + i)->ci = num3;
}
//输出题目的数据
cout << "城市数量\t线路数量\t出发城市\t目标城市\t汽车油箱容量\n";
cout << ccount << "\t" << rcount << "\t" ;
cout << startc << "\t" << endc << "\t" ;
cout << vehs << "\n";
for (i = 0;i cout << *(Pcity + i) << "\n";
for (i = 0;i cout << (Proad + i)->startc << "\t"<< (Proad + i)->endc << "\t" <ci << endl;
// getchar();
//开始寻找线路
SearchStep sFirst;
sFirst.next = NULL;
sFirst.city = startc;
sFirst.pre = NULL;
sFirst.road = 0;
sFirst.s = vehs;
imaxcost = -1;
DoSearch(&sFirst,rcount,Proad,&imaxcost,Pcity,endc);
//输出结果
cout << "搜索结果为：" << imaxcost << endl;
getchar();
return 0;
}