学步园

      题目是中文的，大意不再敖述。此题是dijkstra 的改进版。平时，用djikstra算法求单纯的单源最短路径时，是在每步中找当前未访问的点中距离最短的（即当前未访问的点中dis[]中最小的）作为下一步对其他点进行松弛的源点。而此题则是在每步中找当前未访问的点中距离最短且花费最少的点作为下一步对其他点进行松弛的源点。具体程序如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std ;
const int MAXN = 1005 ;
const int INF = 0x7fffffff ;
struct Node
{
    int adj ;
    int dist ;
    int cost ;
    Node * next ;
};
Node *vert[MAXN] ;
int vis[MAXN] ;
int dis[MAXN] ;  // 建立距离数组
int cos1[MAXN] ;  // 建立花费数组
int m , n ;
int s , t ;
void dijkstra(int v0)
{
    Node * p ;
    p = vert[v0] ;
    int i ;
    for(i = 1 ; i <= n ; i ++)
    {
        dis[i] = INF ;
        cos1[i] = INF ;
    }
    dis[v0] = 0 ;
    cos1[v0] = 0 ;
    vis[v0] = 1 ;
    int u = v0 ;  // u 为 临时 源点
    int minc = INF ;
    int min ;
    for(i = 1 ; i < n ; i ++)
    {
        p = vert[u] ;
        while(p != NULL)
        {
            int tb ;
            tb = p -> adj ;
            int tc = p -> cost ;
            int td = p -> dist ;
            if(!vis[tb] && td < INF && dis[u] + td <= dis[tb])  // 注意：此处很重要
            {
                if(dis[u] + td == dis[tb])
                {
                    if(cos1[u] + tc < cos1[tb])  // 此处为重点，即当距离相等时，选择花费较少的
                    {
                        cos1[tb] = cos1[u] + tc ;
                    }
                }
                else
                {
                    dis[tb] = dis[u] + td ;
                    cos1[tb] = cos1[u] + tc ;
                }
            }
            p = p -> next ;
        }
        int j ;
        min = INF  ;
        minc = INF ;
        for(j = 1 ; j <= n ; j ++)
        {
            if(!vis[j] && dis[j] <= min )  // 此处是寻找距离最短且花费最少的点作为下一步递推的源点
            {
                if(dis[j] == min)
                {
                    if(cos1[j] <= minc)
                    {
                        minc = cos1[j] ;
                        u = j ;
                    }
                }
                else
                {
                    min = dis[j] ;
                    u = j ;
                    minc = cos1[u] ;
                }
            }
        }
        vis[u] = 1 ;
    }
}
int main()
{
    while (scanf("%d%d",&n ,&m) != EOF)
    {
        if(n == 0 && m == 0)
            break ;
        memset(vert , 0 , sizeof(vis)) ;
        memset(vis , 0 , sizeof(vis)) ;
        memset(dis , 0 , sizeof(dis)) ;
        int i ;
        for(i = 0 ; i < m ; i ++)
        {
            int a , b , t , c;
            scanf("%d%d%d%d", &a , &b , &t , &c ) ;
            Node *p = new Node ;
            p -> adj = b ;
            p -> dist = t ;
            p -> cost = c ;
            p -> next = vert[a] ;
            vert[a] = p ;

            p = new Node ;
            p -> adj = a ;
            p -> dist = t ;
            p -> cost = c ;
            p -> next = vert[b] ;
            vert[b] = p ;
        }
        scanf("%d%d", &s , &t) ;
        dijkstra(s) ;
        printf("%d %d\n" , dis[t] , cos1[t]) ;
    }
    return 0 ;
}