是一个不错的dijkstra练手题。
其实题目要求的只是最短路径，而那个费用是再这条路径上的最少费用；
只要在最短长度时取最小费用；
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
const int INF=1<<28;
struct Node
{
int l,v;
}path[N][N],d[N];
bool s[N];
int min_v;
void Init(int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
path[i][j].l=path[i][j].v=INF;
}
for(i=1;i<=n;i++)
d[i].l=d[i].v=INF;
}
int dijkstra(int first,int last,int n)
{
int i,j,u;
memset(s,false,sizeof(s));
for(i=1;i<=n;i++)
{
d[i].l=path[first][i].l;
d[i].v=path[first][i].v;
}
d[first].l=d[first].v=0;
for(i=0;i<n;i++)
{
int temp=INF;
for(j=1;j<=n;j++)
{
if(!s[j]&&d[j].l<temp)
{
temp=d[j].l;
u=j;
}
}
s[u]=true;
for(j=1;j<=n;j++)
{
if(!s[j]&&d[j].l>d[u].l+path[u][j].l)
{
d[j].l=d[u].l+path[u][j].l;
d[j].v=d[u].v+path[u][j].v;
}
if(!s[j]&&d[j].l==d[u].l+path[u][j].l&&d[j].v>d[u].v+path[u][j].v)//此处判断比较重要
d[j].v=d[u].v+path[u][j].v;
}
}
min_v=d[last].v;
return d[last].l;
}
int main()
{
int n,m,i,a,b,d,p;
int first,last,ans;
while(scanf("%d%d",&n,&m)&&(n+m))
{
Init(n);
for(i=0;i<m;i++)
{
scanf("%d%d%d%d",&a,&b,&d,&p);
if(d<path[a][b].l)
{
path[a][b].l=path[b][a].l=d;//图为无向图
path[a][b].v=path[b][a].v=p;
}
if(d==path[a][b].l&&p<path[a][b].v)//判断关键
path[a][b].v=path[b][a].v=p;
}
scanf("%d%d",&first,&last);
ans=dijkstra(first,last,n);
printf("%d %d\n",ans,min_v);
}
return 0;
}