PAT(A)1030 Travel Plan

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392

思路：
1：dijkstra+pre记录路径
2：dijkstra+DFS路径和花费

代码：

#include<bits/stdc++.h>

using namespace std;
int n,m,s,t;
struct node{
    int ne,v,costn;
    node(int _ne,int _v,int _c):ne(_ne),v(_v),costn(_c){}
};
vector<struct node>edge[1005];
priority_queue<pair<int,int>>q;
int vis[1005]={0};
int d[1005];
int pre[1005]={0};
int cosn[1005]={0};
void dij(){
    memset(d,0x3f,sizeof(d));
    memset(cosn,0x3f,sizeof(cosn));
    memset(pre,-1,sizeof(pre));
    d[s]=0;
    cosn[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=0;i<edge[x].size();i++){
            int y=edge[x][i].ne;
            int len=edge[x][i].v;
            if(d[y]>d[x]+len){
                d[y]=d[x]+len;
                if(!vis[y])
                q.push(make_pair(-d[y],y));
                cosn[y]=cosn[x]+edge[x][i].costn;
                pre[y]=x;
            }
            else if(d[y]==d[x]+len&&cosn[y]>cosn[x]+edge[x][i].costn){
                cosn[y]=cosn[x]+edge[x][i].costn;
                pre[y]=x;
            }
        }
    }
   // cout<<d[t]<<endl;
}
void dfs(int x){
   if(pre[x]==-1){
       cout<<x<<" ";
       return;
   }
   else {
       dfs(pre[x]);
       cout<<x<<" ";
   }
}
int main (){
    int l,r,w,c;
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        cin>>l>>r>>w>>c;
        edge[l].push_back(node(r,w,c));
        edge[r].push_back(node(l,w,c));
    }
    dij();
    dfs(t);
    cout<<d[t]<<" "<<cosn[t];
    return 0;
}

PAT(A)1030 Travel Plan

原文：https://www.cnblogs.com/abestxun/p/14493981.html