2021-03-15
北大 算法基础
深搜之寻路
练习代码:
#include<iostream>
#include<vector>
using namespace std;
int K, N, R, S, D, L, T;//开始城市,到达城市,路长,花费
struct Road {
int d, l, t;
};
vector<vector<Road>> cityMaps(110);//城市邻接表,内vector保存各城市可到达的城市,路长,花费
int minLen = 1 << 30;//到终点的最短路长
int totalLen, totalCost;//到当前节点的路长和花费
int visited[110];//标记已走过的城市
int minL[110][10100];//走到各节点同样花费的最短路长
void Dfs(int s) {
if (s == N) {//到达终点
minLen = min(minLen, totalLen);
return;
}
for (int i = 0; i < cityMaps[s].size(); i ) {
int d = cityMaps[s][i].d;//下一个城市
if (!visited[d]) {
int cost = totalCost cityMaps[s][i].t;//如果走此节点的总花费
if (cost > K) continue;//超支,放弃
if (totalLen cityMaps[s][i].l >= minLen || totalLen cityMaps[s][i].l >= minL[d][cost])
continue;//超过最优路长,超过到d的cost花费的路长,放弃
//符合条件走到d
totalLen = cityMaps[s][i].l;
totalCost = cityMaps[s][i].t;
minL[d][cost] = totalLen;
visited[d] = 1;
Dfs(d);
//恢复走到d前的状态
visited[d] = 0;
totalCost -= cityMaps[s][i].t;
totalLen -= cityMaps[s][i].l;
}
}
}
int main() {
cout << "总金额,总城市数,总路数:";
cin >> K >> N >> R;//总金额,总城市数,总路数
cout << endl << "起点数值,到达点,路长,花费:" << endl;
for (int i = 0; i < R; i )
{
int s;//起点
Road r;
cout << i 1 << "): ";
cin >> s >> r.d >> r.l >> r.t;
if (s != r.d)
cityMaps[s].push_back(r);//s城市节点的所有路信息
}
for (int i = 0; i < 110; i )
for (int j = 0; j < 10100; j )
minL[i][j] = 1 << 30;
memset(visited, 0, sizeof(visited));
totalLen = 0;
totalCost = 0;
visited[1] = 1;
minLen = 1 << 30;//最优路长赋极大值
Dfs(1);
if (minLen < (1 << 30))
cout << minLen << endl;
else
cout << "-1" << endl;
return 0;
}
输入输出样例:
赞 (0)