hdu3790 最短路径问题（spfa||dijkstra+两种限制条件）

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

题意：多了一个花费的限制条件，距离相等则选花费少的。

思路：直接在原来的判断条件上加就行，不要想太多。注意有重边。

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 1005;
const int INF = 0x3f3f3f3f;

int dis[N], cost[N], G1[N][N], G2[N][N], n;
bool vis[N];

void dijkstra(int s)
{
    for(int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        cost[i] = INF;
    }
    dis[s] = 0;
    cost[s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int k = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && (k==-1 || dis[j]<dis[k] || (dis[j]==dis[k]&&(cost[j]<cost[k]))))
                k = j;
        }
        if(k == -1) break;
        vis[k] = true;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && (dis[k]+G1[k][j]<dis[j] || (dis[k]+G1[k][j]==dis[j]&&(cost[k]+G2[k][j]<cost[j]))))
            {
                dis[j] = dis[k]+G1[k][j];
                cost[j] = cost[k]+G2[k][j];
            }
        }
    }
}

void spfa(int s)
{
    queue<int>que;
    for(int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        cost[i] = INF;
    }
    dis[s] = 0;
    cost[s] = 0;
    vis[s] = true;
    que.push(s);
    while(!que.empty())
    {
        int now = que.front();
        que.pop();
        vis[now] = false;
        for(int i = 1; i <= n; i++)
        {
            if(dis[now]+G1[now][i]<dis[i] || (dis[now]+G1[now][i]<dis[i]&&(cost[now]+G2[now][i]<cost[i])))
            {
                dis[i] = dis[now]+G1[now][i];
                cost[i] = cost[now]+G2[now][i];
                if(!vis[i])
                {
                    vis[i] = true;
                    que.push(i);
                }
            }
        }
    }
}

int main()
{
  //  freopen("in.txt", "r", stdin);
    int m, u, v, s, t, w1, w2;
    while(~scanf("%d%d", &n, &m))
    {
        if(n == 0 && m == 0) break;
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                {
                    G1[i][j] = 0;
                    G2[i][j] = 0;
                }
                else
                {
                    G1[i][j] = INF;
                    G2[i][j] = INF;
                }
            }
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &u, &v, &w1, &w2);
            if(w1<G1[u][v] || (w1==G1[u][v]&&w2<G2[u][v]))
            {
                G1[u][v] = G1[v][u] = w1;
                G2[u][v] = G2[v][u] = w2;
            }
        }
        scanf("%d%d", &s, &t);
      //  dijkstra(s);
        spfa(s);
        printf("%d %d\n", dis[t], cost[t]);
    }
    return 0;
}