HDU 3790 最短路径问题(Dijkstra)

HDU 3790 最短路径问题(Dijkstra)

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

题意: 

        给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

分析:

        本题直接用Dijkstra计算即可,不过更新的过程中如果对于距离相同的情况,需要对于花费,且还需要更新花费.

        其实本题就是二维目标条件，也可以把权值设计成一个二维的对象，然后自定义小于比较操作即可。

AC代码:

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define INF 1e9
const int maxn = 1000+10;
int n,m;

struct Edge
{
    int from,to,dist,cost;
    Edge(int f,int t,int d,int c):from(f),to(t),dist(d),cost(c){}
};

struct HeapNode
{
    int d,c,u;
    HeapNode(int d,int c,int u):d(d),c(c),u(u){}
    bool operator<(const HeapNode&rhs)const
    {
        return d>rhs.d || (d==rhs.d && c>rhs.c);
    }
};

struct Dijkstra
{
   int n,m;
   vector<Edge> edges;
   vector<int> G[maxn];
   bool done[maxn];
   int d[maxn];
   int c[maxn];

   void init(int n)
   {
       this->n=n;
       for(int i=0;i<n;i++) G[i].clear();
       edges.clear();
   }

   void AddEdge(int from,int to,int dist,int cost)
   {
       edges.push_back(Edge(from,to,dist,cost));
       m = edges.size();
       G[from].push_back(m-1);
   }

   void dijkstra(int s)
   {
       priority_queue<HeapNode> Q;
       for(int i=0;i<n;i++) d[i]=INF,c[i]=INF;
       d[s]=c[s]=0;
       Q.push(HeapNode(d[s],c[s],s));
       memset(done,0,sizeof(done));

       while(!Q.empty())
       {
           HeapNode x= Q.top(); Q.pop();
           int u =x.u;
           if(done[u]) continue;
           done[u]= true;

           for(int i=0;i<G[u].size();i++)
           {
               Edge &e=edges[G[u][i]];
               if(d[e.to] > d[u]+e.dist || (d[e.to]== d[u]+e.dist&&c[e.to]>c[u]+e.cost)  )
               {
                   d[e.to]= d[u]+e.dist;
                   c[e.to]= c[u]+e.cost;
                   Q.push(HeapNode(d[e.to],c[e.to],e.to));
               }
           }
       }
   }
}DJ;

int main()
{
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        DJ.init(n);
        for(int i=0;i<m;i++)
        {
            int u,v,d,c;
            scanf("%d%d%d%d",&u,&v,&d,&c);
            u--,v--;
            DJ.AddEdge(u,v,d,c);
            DJ.AddEdge(v,u,d,c);
        }
        int s,e;
        scanf("%d%d",&s,&e);
        s--,e--;
        DJ.dijkstra(s);
        printf("%d %d\n",DJ.d[e],DJ.c[e]);
    }
    return 0;
}