PAT A1030 Travel Plan

题目链接

Dijkstra+DFS算法

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int INF=1e9;
const int maxn=510;
int n,m,start,dest,optvalue=INF;
int G[maxn][maxn],C[maxn][maxn],d[maxn];
bool vis[maxn]={false};
vector<int> pre[maxn];//记录最短路径
vector<int> path,temp;

void Dijkstra(int s){
    fill(d,d+maxn,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u]+G[u][v]==d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
//DFS找最优路径
void DFS(int s){
    //递归边界
    if(s==start){
        temp.push_back(s);
        //遍历temp，计算路径上的总cost
        int value=0;
        for(int i=temp.size()-1;i>0;i--){
            value+=C[temp[i]][temp[i-1]];
        }
        if(value<optvalue){
            optvalue=value;
            path=temp;
        }
        temp.pop_back();
        return;
    }
    //递归式
    temp.push_back(s);
    for(int i=0;i<pre[s].size();i++){
        DFS(pre[s][i]);
    }
    temp.pop_back();
}


int main(){
    scanf("%d%d%d%d",&n,&m,&start,&dest);
    fill(G[0],G[0]+maxn*maxn,INF);
    fill(C[0],C[0]+maxn*maxn,INF);
    int c1,c2,dis,cost;
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&c1,&c2,&dis,&cost);
        G[c1][c2]=G[c2][c1]=dis;
        C[c1][c2]=C[c2][c1]=cost;
    }

    Dijkstra(start);
    DFS(dest);

    for(int i=path.size()-1;i>=0;i--){
        printf("%d ",path[i]);
    }
    printf("%d %d",d[dest],optvalue);

    return 0;
}

Dijkstra算法

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=510;
const int INF=1e9;
int n,m,st,ed;
int G[maxn][maxn],cost[maxn][maxn],d[maxn],pre[maxn],c[maxn]={0};
bool vis[maxn]={false};

void Dijkstra(int s){
    fill(d,d+maxn,INF);
    d[s]=0;
    c[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    c[v]=c[u]+cost[u][v];
                    pre[v]=u;
                }else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
                    c[v]=c[u]+cost[u][v];
                    pre[v]=u;
                }
            }
        }
    }
}

void DFS(int v){
    if(v==st){
        printf("%d ",v);
        return;
    }
    DFS(pre[v]);
    printf("%d ",v);
}

int main(){
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    int c1,c2,dis,ct;
    fill(G[0],G[0]+maxn*maxn,INF);
    fill(cost[0],cost[0]+maxn*maxn,INF);
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&c1,&c2,&dis,&ct);
        G[c1][c2]=G[c2][c1]=dis;
        cost[c1][c2]=cost[c2][c1]=ct;
    }
    Dijkstra(st);
    DFS(ed);
    printf("%d %d",d[ed],c[ed]);

    return 0;
}