程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3790 最短路徑問題(兩個限制條件的最短路)

hdu 3790 最短路徑問題(兩個限制條件的最短路)

編輯：C++入門知識

有兩個條件：距離和花費。首先要求距離最短，距離相等的條件下花費最小。

dijkstra，只是在判斷條件時多考慮了花費。

注意重邊。

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1010;
int Map[maxn][maxn],cost[maxn][maxn];
int n,m;
int dis1[maxn],dis2[maxn];

void init()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
            {
               Map[i][j] = 0;
               cost[i][j] = 0;
            }
            else
            {
                Map[i][j] = INF;
                cost[i][j] = INF;
            }
        }
    }
}

void dijkstra(int s, int t)
{
    int vis[maxn];
    memset(dis1,INF,sizeof(dis1));
    memset(dis2,INF,sizeof(dis2));
    memset(vis,0,sizeof(vis));

    for(int i = 1; i <= n; i++)
    {
        dis1[i] = Map[s][i];
        dis2[i] = cost[s][i];
    }
    vis[s] = 1;

    for(int i = 1; i <= n; i++)
    {
        int M1= INF, M2 = INF, pos;

        for(int j = 1; j <= n; j++)
        {
            if(vis[j]) continue;
            if(dis1[j] < M1 || (dis1[j] == M1 && dis2[j] < M2))
            {
                M1 = dis1[j];
                M2 = dis2[j];
                pos = j;
            }
        }

        vis[pos] = 1;

        for(int j = 1; j <= n; j++)
        {
            if(vis[j]) continue;
            int tmp1 = dis1[pos] + Map[pos][j];
            int tmp2 = dis2[pos] + cost[pos][j];
            if(tmp1 < dis1[j] || (tmp1 == dis1[j] && tmp2 < dis2[j]))
            {
                dis1[j] = tmp1;
                dis2[j] = tmp2;
            }
        }
    }
}

int main()
{
    while(~scanf(%d %d,&n,&m))
    {
        if(n == 0 || m == 0) break;
        init();
        int a,b,d,p;
        while(m--)
        {
            scanf(%d %d %d %d,&a,&b,&d,&p);
            if(Map[a][b] == INF && cost[a][b] == INF)
            {
                Map[a][b] = Map[b][a] = d;
                cost[a][b] = cost[b][a] = p;
            }
            else if(d < Map[a][b] || (Map[a][b] == d && cost[a][b] > p))
            {
                Map[a][b] = Map[b][a]= d;
                cost[a][b] = cost[b][a] = p;
            }
        }
        scanf(%d %d,&a,&b);
        dijkstra(a,b);
        printf(%d %d
,dis1[b],dis2[b]);
    }
    return 0;
}