[cpp]
#include
#include
typedef struct node
{
int length,cost;
}node;
node A[600][600];
int visited[600];
node T[600];
int Stack[600][600];
int top[600];
int main()
{
int n,m,i,j,s,t,a,b,length,cost,minlength,mincost,fmin,k;
scanf("%d %d %d %d",&n,&m,&s,&t);
for(i=0;i
{
for(j=0;j
A[i][j].length=INT_MAX;
visited[i]=0;
T[i].length=INT_MAX;
T[i].cost=INT_MAX;
top[i]=0;
}
for(i=0;i
{
scanf("%d %d %d %d",&a,&b,&length,&cost);
if(length
while(i!=t)
{
A[a][b].length=length;
A[a][b].cost=cost;
}
A[b][a].length=A[a][b].length;
A[b][a].cost=A[a][b].cost;
}
visited[s]=1;
T[s].length=0;
T[s].cost=0;
i=s;
top[s]=1;
Stack[s][0]=s;
{
for(j=0;j
{
if(visited[j]==0)
{
if(A[i][j].length!=INT_MAX)
{
if(T[i].length+A[i][j].length
{
T[j].length=T[i].length+A[i][j].length;
T[j].cost=T[i].cost+A[i][j].cost;
top[j]=top[i];
for(k=0;k
Stack[j][k]=Stack[i][k];
}
}
}
}
minlength=INT_MAX;
mincost=INT_MAX;
for(j=0;j
{
if(visited[j]==0&&(T[j].length
{
fmin=j;
minlength=T[j].length;
mincost=T[j].cost;
}
}
visited[fmin]=1;
Stack[fmin][top[fmin]++]=fmin;
i=fmin;
}
for(i=0;i
printf("%d ",Stack[t][i]);
printf("%d %d\n",T[t].length,T[t].cost);
return 0;
}