ZOJ Highway Project(dijkstra&heap&邻接表)

题目链接：146 - The 13th Zhejiang Provincial Collegiate Programming Contest - K Highway Project

题意

有n个城市，0是首都，其他编号为1~n-1。
给定m条可以修建的道路，xi, yi, di, ci。表示从x到y需要di秒时间，并且该路需要花费ci$。
现在国王想要一个修建方案，使得他从首都到其他城市花费时间最少，在多种方案花费时间相等的情况下，修建道路所花费的钱最少。

思路

显然，是一个最短路问题。但是题目的数据范围很大，n最大是100000。矩阵是开不了了，只能邻接表。
用了邻接表后，提交发现超时，于是改用优先队列优化，方过。
思路上没什么可说的，就是写起来麻烦些。

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <queue>
using namespace std;
#define LL long long
const int N = 100009;
int head[N];
struct Node
{
    LL u, v, d, c, next;
}e[N*2];
bool vis[N];
struct P
{
    LL i, d, c;
    bool operator <(const P &t) const
    {
        if(this->d == t.d)
            return this->c > t.c;
        return this->d > t.d;
    }
};

P dis[N];
void dijk(int n)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));


    priority_queue<P> q;
    P s = {0, 0, 0};
    q.push(s);
    LL d, c;
    d = c = 0;

    while(!q.empty())
    {
        P mi = q.top();
        q.pop();
        if(vis[mi.i])
            continue;
        vis[mi.i] = 1;

        d += mi.d;
        c += mi.c;

        for(LL i=head[mi.i]; i!=-1; i=e[i].next)
        {
            LL v = e[i].v;
            if(vis[v])
                continue;
            if(mi.d+e[i].d < dis[v].d)
            {
                dis[v].d = mi.d+e[i].d;
                dis[v].c = e[i].c;
                dis[v].i = v;
                q.push(dis[v]);
            }
            else if(mi.d+e[i].d == dis[v].d && e[i].c < dis[v].c)
            {
                dis[v].c = e[i].c;
                dis[v].i = v;
                q.push(dis[v]);
            }
        }
    }
    printf("%lld %lld\n", d, c);
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(head, -1, sizeof(head));
        int n, m;
        scanf("%d%d", &n, &m);
        int pos = 0;
        for(int i=0; i<m; i++)
        {
            int a, b, c, d;
            scanf("%d%d%d%d", &a, &b, &d, &c);
            e[pos].u = a;e[pos].v = b;e[pos].d = d; e[pos].c = c;
            e[pos].next = head[e[pos].u];
            head[e[pos].u] = pos;
            pos++;
            e[pos].u = b;e[pos].v = a;e[pos].d = d; e[pos].c = c;
            e[pos].next = head[e[pos].u];
            head[e[pos].u] = pos;
            pos++;
        }
        dijk(n);
    }
    return 0;
}