PAT甲级1030 Travel Plan (30分)

Myth丶恋晨 2023-06-26 10:58 27阅读 0赞

##### 题解： #####

题目大意是告诉你每个城市间的距离和开销，让你求出从起点到终点的最短距离，然后如果距离相同的话要最小开销，最后输出这条最短的路径、最小距离和最小开销

##### 思路： #####

finalmin记录最后最短路，curpath记录当前路径，cost和len分别记录两两城市间的开销和距离，visit是访问标记  
dfs从起点开始深搜遍历所有可能，到达终点后判断是否是最短距离  
1.小于最短距离，更新数据  
2.等于最短距离，如果开销比较小，更新数据  
实现过程中注意回溯，从一个点开始，遍历完从这个点开始的之后的每一个点后，访问标记设为0，curpath中将当前点删除

##### 代码 #####

#include<iostream>
    #include<vector>
    using namespace std;
    vector<vector<int> > cost,len;
    vector<int>  finalmin,curpath;//存储最短路径
    int m,n,s,d;
    int mindis=999999999,mincost=999999999;
    vector<int> visit;
    void dfs(int cur,int ccost,int cdis)
    { 
        curpath.push_back(cur);
        if(cur==d)//到达终点
        { 
            if(cdis<mindis)
            { 
                mindis=cdis;
                mincost=ccost;
                finalmin=curpath;
            }
            else if(cdis==mindis)
            { 
                if(ccost<mincost)
                { 
                    mincost=ccost;
                    finalmin=curpath;
                }
            }
        }
        visit[cur]=1;
        for(int i=0;i<n;i++)
        { 
            if(len[cur][i]!=0&&!visit[i])
            dfs(i,ccost+cost[cur][i],cdis+len[cur][i]);
        }
        //回溯
        visit[cur]=0;
        curpath.pop_back();
    }
    int main()
    { 
        cin>>n>>m>>s>>d;
        cost.resize(n+5,vector<int>(n+5,0));
        len.resize(n+5,vector<int>(n+5,0));
        visit.resize(n+5,0);
        for(int i=0;i<m;i++)//读入数据
        { 
            int c1,c2,dis,cost1;
            cin>>c1>>c2>>dis>>cost1;
            cost[c1][c2]=cost[c2][c1]=cost1;
            len[c1][c2]=len[c2][c1]=dis;
        }
        dfs(s,0,0);
        for(int i=0;i<finalmin.size();i++)//输出路径
        { 
            cout<<finalmin[i]<<" ";
        }
        cout<<mindis<<" "<<mincost;
        return 0;
    }