1 //3790 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <queue> 7 const int INF = 1 << 28 ; 8  9 using namespace std;10 11 int n, m,s,t;12 int cost[1100][1100] ,mapp[1100][1010];13 int dist[1100],cost1[1100] ;14 int vis[1100] ;15 16 void spfa(int src)17 {18     queue<int> Q ;19     memset(vis,0,sizeof(vis)) ;20     for(int i = 1 ; i <= n ; i++)21     {22         dist[i] = INF ;23         cost1[i] = INF ;24     }25     dist[src] = 0 ;26     vis[src] = 1 ;27     cost1[src] = 0;28     Q.push(src) ;29     while(!Q.empty())30     {31         int u = Q.front() ;32         Q.pop() ;33         vis[u] = 0;34         for(int i = 1 ; i <= n ; i++)35         {36 37             if(dist[i] > dist[u] + mapp[u][i])38             {39                 dist[i] = dist[u] + mapp[u][i] ;40                 cost1[i] = cost1[u] + cost[u][i] ;41                 if(!vis[i])42                 {43                     vis[i] = 1 ;44                     Q.push(i) ;45                 }46             }47             else if(dist[i] == dist[u]+mapp[u][i])48             {49                 if(cost1[i] > cost1[u] + cost[u][i])50                 {51                     cost1[i]=cost1[u] + cost[u][i];52                     if(!vis[i])53                     {54                         vis[i] = 1 ;55                         Q.push(i) ;56                     }57                 }58 59             }60         }61     }62 }63 void Init()64 {65     for(int i = 1 ; i <= n ; i++)66         for(int j = 1 ; j <= n ; j++)67         {68             if(i == j) mapp[i][j] = cost[i][j] = 0 ;69             else mapp[i][j] = cost[i][j] = INF ;70         }71 }72 int main()73 {74     //75     while(cin >> n >> m)76     {77         if(n == 0 && m == 0) break ;78         int a, b , d , p ;79         Init() ;80         for(int i = 0 ; i < m ; i++)81         {82             cin >> a >> b >> d >> p ;83             if(mapp[a][b] > d)84             {85                 mapp[a][b] = mapp[b][a] = d ;86                 cost[a][b] = cost[b][a] = p ;87             }88             else if(mapp[a][b] == d&&cost[a][b] > p)89                 cost[a][b] = cost[b][a] = p ;90         }91         cin >> s >> t ;92         spfa(s) ;93         printf("%d %d\n",dist[t],cost1[t]) ;94     }95     return 0;96 }

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1001 5 using namespace std; 6 const int inf=1<<28; 7  8 int g[maxn][maxn]; 9 int cost[maxn][maxn];10 int n,m,a,b,d,p,s,e;11 bool vis[maxn];12 int dis[maxn],c[maxn];13 14 void inti()15 {16     for(int i=1; i<=n; i++)17     {18         for(int j=1; j<=n; j++)19         {20             if(i==j)21             {22                 g[i][j]=0;23                 cost[i][j]=0;24             }25             else26             {27                 g[i][j]=inf;28                 cost[i][j]=inf;29             }30         }31     }32 }33 34 void dijkstra(int str)35 {36     memset(vis,false,sizeof(vis));37     for(int i=1; i<=n; i++)38     {39         dis[i]=g[str][i];40         c[i]=cost[str][i];41     }42     dis[str]=0;43     c[str]=0; vis[str]=true;44     for(int i=1; i<n; i++)45     {46         int m=inf,x;47         for(int y=1; y<=n; y++)  if(!vis[y]&&dis[y]<m) m=dis[x=y];48         vis[x]=true;49         for(int y=1; y<=n; y++)50         {51             if(!vis[y]&&g[x][y]!=inf)52             {53                 if(dis[y]>dis[x]+g[x][y])54                 {55                     dis[y]=dis[x]+g[x][y];56                     c[y]=c[x]+cost[x][y];57                 }58                 else if(dis[y]==dis[x]+g[x][y])59                 {60                     if(c[y]>c[x]+cost[x][y])61                         c[y]=c[x]+cost[x][y];62                 }63             }64         }65     }66 }67 int main()68 {69     while(scanf("%d%d",&n,&m)!=EOF)70     {71         if(n==0&&m==0) break;72         inti();73         for(int i=0; i<m; i++)74         {75             scanf("%d%d%d%d",&a,&b,&d,&p);76             if(d<g[a][b])77             {78                 g[a][b]=g[b][a]=d;79                 cost[a][b]=cost[b][a]=p;80             }81 82         }83         scanf("%d%d",&s,&e);84         dijkstra(s);85         printf("%d %d\n",dis[e],c[e]);86     }87     return 0;88 }