HDU-3790: 最短路径问题

最短路

Description

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

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1

Output
输出 一行有两个数， 最短距离及其花费。

Sample Input

3 2
1 2 5 6
2 3 4 5
1 3
0 0

Sample Output

9 11

注意的地方：题意是说，首先要保证路径最短，然后在保证路径最短的情况下保证花费最少。不要理解错题目的意思了。

• 结构体重载：在结构体重载的时候，如果路程长度一样，选择花费少的，否则选择路径更短的。

friend bool operator <(node x,node y) //结构体重载
{
    if(x.len==y.len)
        return x.val>y.val;
    return x.len>y.len;
}

• dijkstra：初始化dis和pay都要最大值。若距离可以松弛，不仅要更新dis使它更短，同时也要更新pay，最开始智障地忘了更新，距离不能松弛，判断花费。

if(dis[next.en]>now.len+next.len)
{
    dis[next.en]=now.len+next.len;
    pay[next.en]=now.val+next.val;
    q.push(node(next.en,dis[next.en],pay[next.en])); //注意这里是dis[next.en]和pay[next.en] 最开始写错了……半天找不到问题
}
else if(dis[next.en]==now.len+next.len)
{
    if(pay[next.en]>now.val+next.val)
    {
        pay[next.en]=now.val+next.val;
        q.push(node(next.en,dis[next.en],pay[next.en]));
    }
}

• 完整代码：

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int n,m,vis[1111],dis[1111],pay[1111];
struct node
{
    int en,len,val;
    node(int en1=0,int len1=0,int val1=0)
    {
        en=en1;len=len1;val=val1;
    }
    friend bool operator <(node x,node y)
    {
        if(x.len==y.len)
            return x.val>y.val;
        return x.len>y.len;
    }
};
vector<node> v[1111];
void dij(int st)
{
    dis[st]=0;
    pay[st]=0;
    priority_queue<node>q;
    q.push(node(st,dis[st],pay[st]));
    while(!q.empty())
    {
        node now,next;
        now=q.top();
        q.pop();
        if(vis[now.en]==1)
            continue;
        vis[now.en]=1;
        for(int i=0;i<v[now.en].size();i++)
        {
            next=v[now.en][i];
            if(dis[next.en]>now.len+next.len)
            {
                dis[next.en]=now.len+next.len;
                pay[next.en]=now.val+next.val;
                q.push(node(next.en,dis[next.en],pay[next.en]));
            }
            else if(dis[next.en]==now.len+next.len)
            {
                if(pay[next.en]>now.val+next.val)
                {
                    pay[next.en]=now.val+next.val;
                    q.push(node(next.en,dis[next.en],pay[next.en]));
                }
            }
        }
    }
}
int main()
{
    int a,b,d,p,st,en;
    while(scanf("%d%d",&n,&m),m+n)
    {
        memset(vis,0,sizeof(vis));
        memset(dis,127,sizeof(dis));
        memset(pay,127,sizeof(pay));
        for(int i=0;i<=n;i++)
            v[i].clear();
        while(m--)
        {
            scanf("%d%d%d%d",&a,&b,&d,&p);
            v[a].push_back(node(b,d,p));
            v[b].push_back(node(a,d,p));
        }
        scanf("%d%d",&st,&en);
        dij(st);
        printf("%d %d\n",dis[en],pay[en]);
    }
    return 0;
}