HDU-3790 最短路径问题 （Dijkstra算法优化）

题目传送门

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

这是一道模板题，然而却做了整整一下午，刚开始用的Bellman-Ford的队列优化做的，结果TLE，崩溃:(然后改成了优先队列的，交上去以后MLE，崩溃+1:(今天真的是着实体会了一把从时间超限到内存超限的心痛，内心不甘，去网上搜了题解，发现原来这是一道Dijkstra算法优化的模板题，原谅我的无知，因为在这之前我竟然不知道Dijkstra算法优化，搞了一下午，最终还是搞出来了，心累~~~

首先要定义两个结构体node和edge，便于动态数组vector和优先队列priority_queue数据类型的存储，node结构体要重载运算符<,以便于确认优先队列的优先顺序，然后定义一个数组dis保存路线的长度和花费，接下来就是Dijkstra模板，这道题不仅要输出最短路径，还要输出花费，所以在最短路相同时比较一下花费就好了。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f
const int MAX=1e3+5;
struct node
{
    int to;
    int length;
    int cost;
    node(int _to=0,int _length=0,int _cost=0):to(_to),length(_length),cost(_cost){}
    bool operator <(const node &x)const
    {
        if(length==x.length)
            return cost>x.cost;
        else
            return length>x.length;
    }
};
struct edge
{
    int to;
    int length;
    int cost;
    edge(int _to=0,int _length=0,int _cost=0):to(_to),length(_length),cost(_cost){}
};
struct dist
{
    int way;
    int money;
}dis[MAX];
int n,m;
int main()
{
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        vector <edge> e[MAX];
        for(int i=1;i<=m;i++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            e[a].push_back(edge(b,c,d));
            e[b].push_back(edge(a,c,d));
        }
        int st,en;
        scanf("%d%d",&st,&en);
        for(int i=1;i<=n;i++)
        {
            dis[i].way=inf;
            dis[i].money=inf;
        }
        priority_queue <node> q;
        while(!q.empty())
            q.pop();
        dis[st].money=0;
        dis[st].way=0;
        q.push(node(st,0,0));
        node tmp;
        while(!q.empty())
        {
            tmp=q.top();
            q.pop();
            int u=tmp.to;
            for(int i=0;i<e[u].size();i++)
            {
                int to=e[u][i].to;
                int length=e[u][i].length;
                int cost=e[u][i].cost;
                if(dis[to].way>dis[u].way+length)
                {
                    dis[to].way=dis[u].way+length;
                    dis[to].money=dis[u].money+cost;
                    q.push(node(to,dis[to].way,dis[to].money));
                }
                else if(dis[to].way==dis[u].way+length&&dis[to].money>dis[u].money+cost)
                {
                    dis[to].money=dis[u].money+cost;
                    q.push(node(to,dis[to].way,dis[to].money));
                }
            }
        }
        printf("%d %d
",dis[en].way,dis[en].money);
    }
    return 0;
}