题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=3790
分析：dijkstra没有优化的话，复杂度是n*n，优化后的复杂度是m*logm，n是顶点数，m是边数，所以当边的个数少于n*n时优化后算法效率大大提升，如果大于的话就不能用堆优化了。同时spaf的复杂度比较玄学，尽量不要去使用spaf，我在一道n=3e5，m=3e5的题中使用spaf超时。
AC代码：
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1010,maxm=2*100000+10;
const int INF=1e9+10;
bool ins[maxn];
int dis[maxn],mon[maxn];
int to[maxm],w[maxm],g[maxm],fa[maxn],nex[maxm];
int cnt,n,m;
struct Node{
int x,w,g;
bool operator < (const Node &a)const
{
if(w!=a.w)
return w>a.w;
else return g>a.g;
}
Node(int _x,int _w,int _g):x(_x),w(_w),g(_g){}
};
void add(int a,int b,int c,int d)
{
cnt++;
to[cnt]=b;
w[cnt]=c;
g[cnt]=d;
nex[cnt]=fa[a];
fa[a]=cnt;
}
void spfa(int s,int t)
{
priority_queue<Node>que;
que.push(Node(s,0,0));
for(int i=1;i<=n;i++)
dis[i]=INF,mon[i]=INF;
dis[s]=0,mon[s]=0;
while(que.size())
{
Node now =que.top();
que.pop();
if(ins[now.x])continue;
ins[now.x]=1;
for(int i=fa[now.x];i;i=nex[i])
{
int k=to[i];
if(ins[k])continue;
if(dis[k]>now.w+w[i])
{
dis[k]=now.w+w[i];
mon[k]=now.g+g[i];
que.push(Node(k,dis[k],mon[k]));
}
else if(dis[k]==now.w+w[i]&&mon[k]>now.g+g[i])
{
mon[k]=now.g+g[i];
que.push(Node(k,dis[k],mon[k]));
}
}
}
printf("%d %d
",dis[t],mon[t]);
}
int main()
{
int s,t;
while(scanf("%d %d",&n,&m)==2)
{
if(n==0&&m==0)break;
cnt=0;
memset(ins,0,sizeof(ins));
memset(fa,0,sizeof(fa));
for(int i=1;i<=m;i++)
{
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
add(a,b,c,d);
add(b,a,c,d);
}
scanf("%d %d",&s,&t);
spfa(s,t);
}
}