07-图6 旅游规划（Dijkstra算法(单源最短路径问题)）

Dijkstra算法

“单源最短路径”问题，查找两点之间最短路径

07-图6 旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

输出样例:

3 40

代码

#include<bits/stdc++.h>
using namespace std;
#define Maxn 1000

int a[550][550];
int s[550][550];
int d[550];
int f[550];
int visited[550]={0};
int v,b,n,m;
void Dijkstra(int x){
    for(int i=0;i<v;i++){    //从0到i的路径和费用再次分别存到数组 中 
        d[i]=a[x][i];
        f[i]=s[x][i];
    }
    visited[x]=1;    //不走回头路 
    d[x]=0,f[x]=0;     

    for(int i=1;i<v;i++){
        int tail,j,mm=Maxn;
        for(j=0;j<v;j++){    //每次选出最短路径 
            if(!visited[j]&&d[j]<mm){
                mm=d[j];
                tail=j;
            }
        }
        visited[tail]=1;
        
        for(j=0;j<v;j++){
            if(!visited[j]){
                if(d[tail]+a[tail][j]<d[j]){    //最短路径 
                    d[j]=d[tail]+a[tail][j];
                    f[j]=f[tail]+s[tail][j];
                }else if(d[tail]+a[tail][j]==d[j]    //最少费用 
                &&f[tail]+s[tail][j]<f[j]){
                    f[j]=f[tail]+s[tail][j];
                } 
            }
        }
    }
}
int main(){
    cin>>v>>b>>n>>m;
    for (int i = 0; i < v; i++)    //二维数组里面的内容是最大的 
    for (int j = 0; j < v; j++) {
        a[i][j] = Maxn;
        s[i][j] = Maxn;
    }
    int q,w,e,r;
    for(int i=1;i<=b;i++){    //输入信息 
        cin>>q>>w>>e>>r;
        a[q][w]=a[w][q]=e;
        s[q][w]=s[w][q]=r;
    }
    Dijkstra(n);    //Dijkstra算法 
    cout<<d[m]<<" "<<f[m];
    return 0;
}