[PAT Advanced Level]1030. Travel Plan (30) - c++编程基础

先用Djikstra算出最短路径，纪录下相同的最短路径，再回溯计算花费最少的路径。
其实不用回溯，直接在比较最短路径的时候比较花费最少就可以了。
#include   
#include   
#include   
#include   
using namespace std;  
  
struct node  
{  
    int index;  
    int curDist;  
    vector preCity;  
    node(int c, int d) : index(c), curDist(d) {}  
};  
  
const int MAXINT = 0x7fffffff;  
int n, m, s, d;  
vector> dist;  
vector> cost;  
vector v;  
vector q;  
vector result;  
int totalCost = MAXINT;  
  
bool cmp(const node &n1, const node &n2)  
{  
    return n1.curDist > n2.curDist;  
}  
bool cmp1(const node &n1, const node &n2)  
{  
    return n1.index < n2.index;  
}  
  
void Dijkstra()  
{  
    for(int i = 0; i < n; i++)  
        v.push_back(node(i, MAXINT));  
    v[s].curDist = 0;  
    while (!v.empty())  
    {  
        make_heap(v.begin(), v.end(), cmp);  
        pop_heap(v.begin(), v.end(), cmp);  
        node n = v.back();  
        v.pop_back();  
        for(int i = 0; i < v.size(); i++)  
        {  
            if(dist[n.index][v[i].index] != -1)  
            {  
                int now = dist[n.index][v[i].index] + n.curDist;  
                if(now < v[i].curDist)  
                {  
                    v[i].curDist = now;  
                    v[i].preCity.clear();  
                    v[i].preCity.push_back(n);  
                }  
                else if(now == v[i].curDist)  
                    v[i].preCity.push_back(n);  
            }  
        }  
        q.push_back(n);  
    }  
}  
  
void getPath(int index, int curCost, vector




 &seq)  
{  
    if(q[index].index == s)  
    {  
        if(curCost < totalCost)  
        {  
            totalCost = curCost;  
            result = seq;  
        }  
    }  
    else  
    {  
        for(int i = 0; i < q[index].preCity.size(); i++)  
        {  
            seq.push_back(q[index].preCity[i].index);  
            curCost += cost[index][q[index].preCity[i].index];  
            getPath(q[index].preCity[i].index, curCost, seq);  
            curCost -= cost[index][q[index].preCity[i].index];  
            seq.pop_back();  
        }  
    }  
}  
  
int main()  
{  
//  fstream cin("a.txt");  
    cin>>n>>m>>s>>d;  
    int i = 0;  
    dist = vector>(n, vector(n, -1));  
    cost = vector>(n, vector(n, -1));  
    int t1, t2, t3, t4;  
    while (i < m)  
    {  
        cin>>t1>>t2>>t3>>t4;  
        dist[t1][t2] = dist[t2][t1] = t3;  
        cost[t1][t2] = cost[t2][t1] = t4;  
        i++;  
    }  
    Dijkstra();  
    sort(q.begin(), q.end(), cmp1);  
    vector tmp;  
    getPath(d, 0, tmp);  
    for(vector::reverse_iterator rit = result.rbegin(); rit != result.rend(); rit++)  
        cout<<*rit<<" ";  
    cout<