题解 | #最短路径问题#

#include <iostream>
#include <utility>
#include <cstring>
using namespace std;
#define mm memset
typedef pair<int ,int> pii;
pii m1[1000][1000];
bool visited[1000];

int numsd[1000]; // initial =inf

int numspre[1000]; // previous path
int numsc[1000]; // 
const int INF = 0x3f3f3f3f;

void dijkstra(int s , int e1)
{

    mm(numsd,0x3f,sizeof(numsd));
    mm(numsc,0x3f,sizeof(numsc));
    mm(visited,0,sizeof(visited));
    numsd[s] = 0; numspre[s] = s; numsc[s] = 0;
    while (visited[e1] == false)
    {
        int tmpd = INF, tmpi;
        for(int i= 0; i< 1000 ;++i)
        {
            if(visited[i] == false && numsd[i] < tmpd)
            {
                tmpd = numsd[i]; tmpi =i;
            }
        }
        visited[tmpi] = true; 
        // if(tmpi == e1) return;
        for(int i = 0; i< 1000 ; ++i)
        {
            if(visited[i]==false && 
           ( 
            (numsd[i] > numsd[tmpi] +m1[tmpi][i].first) 
            || 
            (numsd[i] == numsd[tmpi] +m1[tmpi][i].first && numsc[i] > numsc[tmpi] +m1[tmpi][i].second)
           )
           )
            {
                numsd[i] = numsd[tmpi] +m1[tmpi][i].first;
                // numspre[i] = tmpi;
                numsc[i] = numsc[tmpi] +m1[tmpi][i].second;
            }
        }
    }
}

// int fcount(int s,int e1)
// {
//     if(s == e1) return 0;
//     return m1[e1][numspre[e1]].second + fcount(s,numspre[e1]);
// }

int main()
{
    int  n ,m; 
    while (cin>> n >>m)
    {
        if( n== 0) break;
        int a ,b ,d ,p,s, e1;
    
        mm(m1,0x3f,sizeof(m1));
        for(int i= 0 ;i< m ;++ i)
        {
            cin >>a >>b>>d >>p;
            if(d < m1[a-1][b-1].first || (d ==m1[a-1][b-1].first && m1[a-1][b-1].second > p))
            {
                m1[a-1][b-1] = m1[b-1][a-1] ={d,p};
            }
        }
        cin>> s >>e1;
        dijkstra(s-1,e1-1);
        cout<< numsd[e1-1]<<" "<<numsc[e1-1]<<endl;
    }
    
}