1030 Travel Plan (dfs, 旅行者问题，详解)

目录

题目

测试样例

输入样例1

输出样例1

输入样例2（自编）

输出样例2

提交结果截图

带中间数据输出的源代码

样例的中间数据输出

带详细注释的源代码

题目

题目链接：

1030 Travel Planhttps://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392

测试样例

输入样例1

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例1

0 2 3 3 40

输入样例2（自编）

8 9 2 3
1 2 4 20
1 3 5 30
1 4 2 25
2 3 9 90
3 4 1 39
2 5 3 30
5 6 6 40
3 6 3 15
4 6 3 19

输出样例2

2 1 4 3 7 84

提交结果截图

带中间数据输出的源代码

#include 
#include 
#include 
using namespace std;

int n,//num of cities
m,//num of highways
s,//the start city
d,//the destination city
dis[501][501],//dis of two cities
cost[501][501],//cost of highway of two cities
tmp_s,
tmp_d,
tmp_dis,
tmp_cost;

int cur_dis = 0, cur_cost = 0, min_dis = 999999999, min_cost = 999999999;
int vis[501];
vector  res(0), tmp(0);
void find(int i)
{
    // test
    cout << endl << "now, i = " << i << endl;
    for (int i = 0; i < tmp.size(); i++)
        cout << tmp[i] << " ";
    cout << endl;
    if (i == d)
    {
        int flag = false;
        cout << "comparing..." << endl;
        if (cur_dis < min_dis)
        {
            min_dis = cur_dis;
            min_cost = cur_cost;
            res = tmp;//reservet the way
            cout << "changed!" << endl;
            flag = true;
        }
        else if (cur_dis == min_dis && cur_cost < min_cost)
        {
            min_cost = cur_cost;
            res = tmp;//reservet the way
            cout << "changed!" << endl;
            flag = true;
        }
        if (!flag)
            cout << "unchanged!" << endl;
        return;

    }
    else
    {
        for (int j = 0; j < n; j++)
        {
            cout << "j = " << j << endl;
            if (!vis[j] && dis[i][j])
            {
                vis[j] = 1;
                cur_cost += cost[i][j];
                cur_dis += dis[i][j]; 
                cout << "cur_dis = " << cur_dis << endl;
                cout << "cur_cost = " << cur_cost << endl;
                tmp.push_back(j);
                find(j);
                tmp.pop_back();
                cur_cost -= cost[i][j];
                cur_dis -= dis[i][j];
                vis[j] = 0;

            }
        }
    }

}

int main()
{
    cin >> n >> m >> s >> d;
    for (int i = 0; i < m; i++)
    {
        cin >> tmp_s >> tmp_d >> tmp_dis >> tmp_cost;
        //这里容易忽略，路线的相对性，不能只是一方到另一方，而是两方都互通
        dis[tmp_s][tmp_d] = dis[tmp_d][tmp_s] = tmp_dis;
        cost[tmp_s][tmp_d] = cost[tmp_d][tmp_s] = tmp_cost;
    }
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    tmp.push_back(s);
    find(s);
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << min_dis << " " << min_cost << endl;
    return 0;
}

样例的中间数据输出

now, i = 0
0
j = 0
j = 1
cur_dis = 1
cur_cost = 20

now, i = 1
0 1
j = 0
j = 1
j = 2
j = 3
cur_dis = 3
cur_cost = 50

now, i = 3
0 1 3
comparing...
changed!
j = 2
cur_dis = 2
cur_cost = 20

now, i = 2
0 2
j = 0
j = 1
j = 2
j = 3
cur_dis = 3
cur_cost = 40

now, i = 3
0 2 3
comparing...
changed!
j = 3
cur_dis = 4
cur_cost = 10

now, i = 3
0 3
comparing...
unchanged!
0 2 3 3 40

带详细注释的源代码

#include 
#include 
#include 
#include 
using namespace std;

int n,//num of cities
m,//num of highways
s,//the start city
d,//the destination city
dis[501][501],//dis of two cities
cost[501][501],//cost of highway of two cities
tmp_s,
tmp_d,
tmp_dis,
tmp_cost;

int cur_dis = 0, cur_cost = 0, min_dis = 999999999, min_cost = 999999999;
int vis[501];//标记每个城市是否走过
vector  res(0), tmp(0);
void find(int i)//dfs遍历所有路线
{
    if (i == d)//若到达目标城市
    {
        if (cur_dis < min_dis)//若是当前路线的长度最小
        {
            min_dis = cur_dis;
            min_cost = cur_cost;//要记得更新最少的花费
            res = tmp;//reservet the way
        }
        else if (cur_dis == min_dis && cur_cost < min_cost)//路线长度最小且花费最少
        {
            min_cost = cur_cost;
            res = tmp;//reservet the way
        }
        return;

    }
    else
    {
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && dis[i][j])//若j可作为下一个城市（未走过且有通向j的高速公路）
            {
                vis[j] = 1;//标记j城市走过
                cur_cost += cost[i][j];//更新花费
                cur_dis += dis[i][j];//更新路线长度
                tmp.push_back(j);//存储路线
                find(j);//递归下一层
                tmp.pop_back();//路线还原
                cur_cost -= cost[i][j];//花费还原
                cur_dis -= dis[i][j];//路线长度还原
                vis[j] = 0;//取消标记
            }
        }
    }

}

int main()
{
    cin >> n >> m >> s >> d;
    for (int i = 0; i < m; i++)
    {
        cin >> tmp_s >> tmp_d >> tmp_dis >> tmp_cost;
        //这里容易忽略，路线的相对性，不能只是一方到另一方，而是两方都互通
        dis[tmp_s][tmp_d] = dis[tmp_d][tmp_s] = tmp_dis;
        cost[tmp_s][tmp_d] = cost[tmp_d][tmp_s] = tmp_cost;
    }
    memset(vis, 0, sizeof(vis));//初始化为0
    vis[s] = 1;//先将起点城市标记为访问过
    tmp.push_back(s);//先将起点城市存储进路线中
    find(s);//dfs求出最佳路线
    for (int i = 0; i < res.size(); i++)//输出路线
        cout << res[i] << " ";
    cout << min_dis << " " << min_cost << endl;
    return 0;
}