Problem Description
Bob gets tired of playing games, leaves Alice, and travels to Changsha alone. Yuelu Mountain, Orange Island, Window of the World, the Provincial Museum etc...are scenic spots Bob wants to visit. However, his time is very limited, he can’t visit them all.
Assuming that there are N scenic spots in Changsha, Bob defines a satisfaction value Si to each spot. If he visits this spot, his total satisfaction value will plus Si. Bob hopes that within the limited time T, he can start at spot S, visit some spots selectively, and finally stop at spot E, so that the total satisfaction value can be as large as possible. It's obvious that visiting the spot will also cost some time, suppose that it takes Ci units of time to visit spot i ( 0 <= i < N ).
Always remember, Bob can choose to pass by a spot without visiting it (including S and E), maybe he just want to walk shorter distance for saving time.
Bob also has a special need which is that he will only visit the spot whose satisfaction value is strictly larger than that of which he visited last time. For example, if he has visited a spot whose satisfaction value is 50, he would only visit spot whose satisfaction value is 51 or more then. The paths between the spots are bi-directional, of course.
Input
The first line is an integer W, which is the number of testing cases, and the W sets of data are following.
The first line of each test data contains five integers: N M T S E. N represents the number of spots, 1 < N < 100; M represents the number of paths, 0 < M < 1000; T represents the time limitation, 0 < T <= 300; S means the spot Bob starts from. E indicates the end spot. (0 <= S, E < N)
The second line of the test data contains N integers Ci ( 0 <= Ci <= T ), which means the cost of time if Bob visits the spot i.
The third line also has N integers, which means the satisfaction value Si that can be obtained by visiting the spot i ( 0 <= Si < 100 ).
The next M lines, each line contains three integers u v L, means there is a bi-directional path between spot u and v and it takes L units of time to walk from u to v or from v to u. (0 <= u, v < N, 0 <= L <= T)
Output
Output case number in the first line (formatted as the sample output).
The second line contains an integer, which is the greatest satisfaction value.
If Bob can’t reach spot E in T units of time, you should output just a “0” (without quotation marks).
Sample Input
1
4 4 22 0 3
1 1 1 1
5 7 9 12
0 1 10
1 3 10
0 2 10
2 3 10
Sample Output
Case #1:
21
五城市旅行商算法~~~
#include<iostream>
using namespace std;
#define n 4
int main()
{
int i,j,k,l;
int S[n];//用于存储已访问过的城市
int D[n][n];//用于存储两个城市之间的距离
int sum = 0;//用于记算已访问过的城市的最小路径长度
int Dtemp;//保证Dtemp比任意两个城市之间的距离都大（其实在算法描述中更准确的应为无穷大）
int flag;////最为访问的标志，若被访问过则为1，从未被访问过则为0
/*初始化*/
i = 1;//i是至今已访问过的城市
S[0] = 0;
D[0][1] = 2;D[0][2] = 6;D[0][3] = 5;D[1][0] = 2;D[1][2] = 4;
D[1][3] = 4;D[2][0] = 6;D[2][1] = 4;D[2][3] = 2;D[3][0] = 5;
D[3][1] = 4;D[3][2] = 2;
do{
k = 1;Dtemp = 10000;
do{
l = 0;flag = 0;
do{
if(S[l] == k){//判断该城市是否已被访问过，若被访问过，
flag = 1;//则flag为1
break;//跳出循环，不参与距离的比较
}else
l++;
}while(l < i);
if(flag == 0&&D[k][S[i - 1]] < Dtemp){/*D[k][S[i - 1]]表示当前未被访问的城市k与上一个已访问过的城市i-1之间的距离*/
j = k;//j用于存储已访问过的城市k
Dtemp = D[k][S[i - 1]];//Dtemp用于暂时存储当前最小路径的值
}
k++;
}while(k < n);
S[i] = j;//将已访问过的城市j存入到S[i]中
i++;
sum += Dtemp;//求出各城市之间的最短距离，注意：在结束循环时，该旅行商尚未回到原出发的城市
}while(i < n);
sum += D[0][j];//D[0][j]为旅行商所在的最后一个城市与原出发的城市之间的距离
for(j = 0; j < n; j++){ //输出经过的城市的路径
cout<<j<<" ";
}
cout<<"\n"<<sum;//求出最短路径的值
}