输入

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出

0 2 3 3 40

程序

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

//最大顶点数 
const int MAXV=510;

const int INF=0x3fffffff;

//n为顶点数，m为边数，st和ed分别为起点和终点
//G为距离矩阵，cost为花费矩阵
//d[]记录最短距离，c[]记录最小花费

int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
int d[MAXV],c[MAXV],pre[MAXV];
bool vis[MAXV]={
  false};


//S为起点 
void Dijkstra(int s)
{
    fill(d,d+MAXV,INF);
    fill(c,c+MAXV,INF);

    for(int i=0;i<n;i++)
    {

        pre[i]=i;

    }

    d[s]=0;
    c[s]=0;

    for(int i=0;i<n;i++)
    {

        int u=-1,MIN=INF;

        for(int j=0;j<n;j++)
        {
            if( vis[j]==false && d[j]<MIN )
            {
                u=j;
                MIN=d[j];


            }


        }

        if(u==-1)
        {
            return;

        }


        vis[u]=true;

        for(int v=0;v<n;v++)
        {
            if( vis[v]==false && G[u][v]!=INF  )
            {
                if( d[u]+G[u][v]<d[v] )
                {
                    d[v]=d[u]+G[u][v];
                    c[v]=c[u]+cost[u][v];

                    pre[v]=u;

                }
                else if( d[u]+G[u][v]==d[v]  )
                {

                    if( c[u]+cost[u][v]<c[v]  )
                    {
                        c[v]=c[u]+cost[u][v];

                        pre[v]=u;
                    }


                }





            }

        }







    }






}


//打印路径 
void DFS(int v)
{


    if(v==st)
    {
        printf("%d",v);
        return;

    }



    DFS(pre[v]);
    printf(" %d",v);



} 



int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);

    int u,v;

    //初始化图G 
    fill(G[0],G[0]+MAXV*MAXV,INF);

    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        scanf("%d%d",&G[u][v],&cost[u][v]);

        G[v][u]=G[u][v];
        cost[v][u]=cost[u][v];



    }


    //迪杰斯特拉算法入口 
    Dijkstra(st);

    //打印路径 
    DFS(ed);

    //最短距离、最短路径下的最小花费 
    printf(" %d %d\n",d[ed],c[ed]);

    return 0;


}