Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

 

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)

 

Output

输出 一行有两个数， 最短距离及其花费。

 

Sample Input

 

Sample Output

8 10

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int oo=;

 int **weight,**profit;//权值和花费

 int s,e;

 int n,m;

 int *low,*vis,*lowp,*pre;

 int**Apply_space(int n)

 {

     int **p;

     p=new int*[n+];

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

     p[i]=new int[n+];

     return p;

 }

 void dijkstra()

 {

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

     {

         low[i]=weight[s][i];

         lowp[i]=profit[s][i];

         pre[i]=s;//初始化路径

     }

     low[s]=lowp[s]=;

     vis[s]=;

     pre[s]=;

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

     {

         int v;

         int Min=oo;

         for(int j=;j<=n;j++)

             if(!vis[j]&&low[j]<Min)

             {

                 Min=low[j];

                 v=j;

             }

         vis[v]=;

         for(int j=;j<=n;j++)

         {

         if(!vis[j]&&low[j]>low[v]+weight[v][j])

             {

                 low[j]=low[v]+weight[v][j];

                 lowp[j]=lowp[v]+profit[v][j];

                 pre[j]=v;//标记路径

             }

         else if(!vis[j]&&low[j]==low[v]+weight[v][j])

         {

             if(lowp[j]>=lowp[v]+profit[v][j])

             {

                 lowp[j]=lowp[v]+profit[v][j];

                 pre[j]=v;//标记路径

             }

         }

         }

     }

 }

 void dfs(int i)//输出路径

 {

     if(pre[i]==)

     {

         cout<<i<<" ";

         return;

     }

     int j=pre[i];

     dfs(j);

     cout<<i<<" ";

 }

 int main()

 {

     while(scanf("%d %d",&n,&m)==&&(n||m))

     {

         profit=Apply_space(n);

         weight=Apply_space(n);

         low=new int[n+];

         vis=new int[n+];

         lowp=new int[n+];

         pre=new int[n+];

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

         {

             vis[i]=;

         }

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

         for(int j=;j<=n;j++)

         {

             profit[i][j]=(i==j)?:oo;

             weight[i][j]=(i==j)?:oo;

         }

         int a,b,c,d;

         for(int i=;i<=m;i++)

         {

             scanf("%d %d %d %d",&a,&b,&c,&d);

             if(weight[a][b]>c)

             {

                 weight[a][b]=weight[b][a]=c;

                 profit[a][b]=profit[b][a]=d;

             }

             else if(weight[a][b]==c)

             {

                 if(profit[a][b]>d)

                 {

                     profit[a][b]=profit[b][a]=d;

                 }

             }

         }

         scanf("%d %d",&s,&e);

         dijkstra();

         printf("%d %d\n",low[e],lowp[e]);

         //dfs(e);//记录路径使用

         delete []profit;delete []weight;delete []low;delete []vis;

         delete []pre;

     }

     return ;

 }