hdu 3790 最短路径问题(两个限制条件的最短路)

http://acm.hdu.edu.cn/showproblem.php?pid=3790

有两个条件：距离和花费。首先要求距离最短，距离相等的条件下花费最小。

dijkstra，仅仅是在推断条件时多考虑了花费。

注意重边。

#include <stdio.h>

#include <algorithm>

#include <set>

#include <map>

#include <vector>

#include <math.h>

#include <string.h>

#include <stack>

#include <queue>

#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\n",dis1[b],dis2[b]);

    }

    return 0;

}