pta7-7旅游规划（dijkstra算法）

题目链接：https://pintia.cn/problem-sets/1101307589335527424/problems/1101314114762387456

题意：给n给城市，m条公路，公路是双向的，起点S，终点D，并给出每条公路连接的两个city的编号以及路费，求S到D的最短距离，若具有最短距离的路线不止一条，求出路费最少的一条。

思路：单源最短路径问题，利用dijkstra算法求出S到其他点的最短路径，只不过加一个路费cost，在dis相等的情况下，取cost最小值。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int inf=0x3f3f3f3f;

int n,m,S,D;

int dis[],cost[],a[][],b[][],vis[];

void dijkstra(){

    vis[S]=;

    for(int i=;i<n-;++i){

        int Min=inf,k;

        for(int i=;i<n;++i)

            if(!vis[i]&&dis[i]<Min)

                Min=dis[i],k=i;

        if(Min==inf) break;

        vis[k]=;

        for(int i=;i<n;++i)

            if(!vis[i]&&dis[i]>dis[k]+a[k][i]){

                dis[i]=dis[k]+a[k][i];

                cost[i]=cost[k]+b[k][i];

            }

            else if(!vis[i]&&dis[i]==dis[k]+a[k][i]&&cost[i]>cost[k]+b[k][i])

                cost[i]=cost[k]+b[k][i];

    }

}

int main(){

    scanf("%d%d%d%d",&n,&m,&S,&D);

    for(int i=;i<n;++i)

        for(int j=;j<n;++j)

            a[i][j]=b[i][j]=inf;

    int t1,t2,t3,t4;

    while(m--){

        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);

        a[t1][t2]=a[t2][t1]=t3;

        b[t1][t2]=b[t2][t1]=t4;

    }

    for(int i=;i<n;++i)

        dis[i]=a[S][i],cost[i]=b[S][i];

    dis[S]=cost[S]=;

    dijkstra();

    printf("%d %d\n",dis[D],cost[D]);

    return ;

}

巴特西

pta7-7旅游规划（dijkstra算法）

最新文章

热门文章