#include <iostream>
#include <queue>
#include <cstdio>
#define INF 10000000
using namespace std;
struct node
{
int dis,cost;
};
struct path
{
int value,cost;
};
node lowcost[1005];
bool inQueue[1005];
path road[1005][1005];
int main()
{
int N,M;
while(scanf("%d%d",&N,&M),N!=0&&M!=0)
{
if(N==0 && M==0)
break;
for(int i=1;i<=N;i++)
{
inQueue[i]=false;
lowcost[i].dis=INF;
lowcost[i].cost=INF;
for(int j=1;j<=N;j++)
{
road[i][j].cost=INF;
road[i][j].value=INF;
}
}
for(int i=1;i<=M;i++)
{
int s,e,v,c;
scanf("%d%d%d%d",&s,&e,&v,&c);
if(road[s][e].value>v)//图矩阵赋值，相连取距离最短，距离相同取费用最少
{
road[s][e].value=v;
road[s][e].cost=c;
road[e][s].value=v;
road[e][s].cost=c;
}
else if(road[s][e].value==v)
{
if(road[s][e].cost>c)
{
road[s][e].value=v;
road[s][e].cost=c;
road[e][s].value=v;
road[e][s].cost=c;
}
}
}
int start,end;
scanf("%d%d",&start,&end);
queue<int> Q;//在这里用链表的好处就是后面进去的一定是后来发现的连通点
lowcost[start].dis=0;//start到自己的最小费用0
lowcost[start].cost=0;
Q.push(start);
inQueue[start]=true;
while(!Q.empty())
{
int temp=Q.front();//对每个与start可连通的点进行搜索
for(int i=1;i<=N;i++)
{
if(i!=temp&&i!=start)
{
if(lowcost[temp].dis+road[temp][i].value<lowcost[i].dis)
//比较起点s到节点x+节点x到节点i的距离是否小于起点s直接到i从而找到一条s到i的最短路 见图片
{
lowcost[i].dis=lowcost[temp].dis+road[temp][i].value;
lowcost[i].cost=lowcost[temp].cost+road[temp][i].cost;
if(inQueue[i]==false)
{
Q.push(i);
inQueue[i]=true;
}
}
else if(lowcost[temp].dis+road[temp][i].value==lowcost[i].dis)
{
if(lowcost[i].cost>road[temp][i].cost+lowcost[temp].cost)
lowcost[i].cost=road[temp][i].cost+lowcost[temp].cost;
}
}
}
Q.pop();
inQueue[temp]=false;
}
if(lowcost[end].dis!=INF)
printf("%d %d
",lowcost[end].dis,lowcost[end].cost);
else
printf("0 0
");
}
return 0;
}
================================哥是分割线=============================
以下是Dijstra算法
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <memory.h>
#include <malloc.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define MAX_SIZE 1001
#define MAX_NUM 10000000
struct edge
{
int d;
int p;
};
edge cost[MAX_SIZE][MAX_SIZE];
int choose(edge * distance,int n, int * found)
{
edge min={MAX_NUM,MAX_NUM};
int minpos=-1;
for(int i=1;i<=n;i++)
{
if(!found[i])
{
if(distance[i].d<min.d)
{
min=distance[i];
minpos=i;
}
else if(distance[i].d == min.d && distance[i].p<min.p)
{
min=distance[i];
minpos=i;
}
}
}
return minpos;
}
edge shotestpath(int v,int t,int n)
{
edge distance[MAX_SIZE];
int found[MAX_SIZE];
for(int i=1;i<=n;i++)
{
distance[i]=cost[v][i];//把每个节点i到初始节点s的距离和花费给distance
found[i]=0;
}
found[v]=1;
distance[v].d=0;
distance[v].p=0;
for(int i=1;i<n-1;i++)
{
int u=choose(distance,n,found);
found[u]=1;
if(u==t)
{
return distance[t];
}
for(int w=1;w<=n;w++)
{
if(!found[w])
{
if(distance[u].d+cost[u][w].d<distance[w].d)
{
distance[w].d=distance[u].d+cost[u][w].d;
distance[w].p=distance[u].p+cost[u][w].p;
}
else if(distance[u].d+cost[u][w].d==distance[w].d
&& distance[u].p+cost[u][w].p<distance[w].p)
{
distance[w].d=distance[u].d+cost[u][w].d;
distance[w].p=distance[u].p+cost[u][w].p;
}
}
}
}
return distance[t];
}
int main()
{
int n,m;
//freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
while(scanf("%d%d",&n,&m) && n+m!=0)
{
for(int i=1;i<=n;i++)//节点初始化
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
cost[i][j].d=0;
cost[i][j].p=0;
}
else
{
cost[i][j].d=MAX_NUM;
cost[i][j].p=MAX_NUM;
}
}
}
int a,b,d,p;
while(m--)
{
scanf("%d%d%d%d",&a,&b,&d,&p);
if(cost[a][b].d>d)//以最小距离初始化节点间距离
{
cost[a][b].d=cost[b][a].d=d;
cost[a][b].p=cost[b][a].p=p;
}
else if(cost[a][b].d==d)
{
if(cost[a][b].p>p)
cost[a][b].p=cost[b][a].p=p;
}
}
int s,t;
scanf("%d%d",&s,&t);
edge e=shotestpath(s,t,n);
if(e.d!=MAX_NUM)
printf("%d %d
",e.d,e.p);
else
printf("0 0
");
}
return 0;
}