PAT-1030. Travel Plan (30)

这道题目就是简单的dijkstra算法，典型的从几条路径中选出一条最优的路径。

disjkstra算法:

1,设初始点d[v]=0;==>findMinIndex（寻找未被访问的最小顶点）>>对该顶点相邻接的顶点进行伸缩(伸缩时候是否考虑顶点被访问呢？当然是要考虑的)

 用pre数组开记录路径，最后用栈来模拟出调用路径。

这道题目的意思就是给你一个图，每一段距离之间距离和cost，求从以顶点到另外一个顶点距离最短的路径，如果存在多条路径最短的路径，那么就选择话费最小的那一条。今天PAT题目最后一道题目好像就是这个的加强版。这个题目只是给了三个测试用例，没啥奇葩数据，1A，爽啊。

后面再加入一个搜索版的。

#include<stdio.h>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
#define MAX 510
//vector<int> map[MAX] 保存一张图的时候可以考虑用vector邻接表的形式
int map[MAX][MAX];
int cost[MAX][MAX];
int dv[MAX];
int cv[MAX];
int pre[MAX];
bool visited[MAX];
int maxInt=0xffffffff>>1;
stack<int> path;
int findMin(int n)
{
    int min=maxInt,index=-1;
    for(int i=0;i<n;i++)
    {
        if(!visited[i]&&dv[i]<min)
        {
            min=dv[i];
            index=i;
        }
    }
    return index;
}
int main()
{
    int n,m,s,d;
    int a,b,dis,cos;
    //freopen("1030-in.txt","r",stdin);
    //freopen("1030-out.txt","w",stdout);
    while(scanf("%d%d%d%d",&n,&m,&s,&d)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
               map[i][j]=maxInt;
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&a,&b,&dis,&cos);
            map[a][b]=map[b][a]=dis;
            cost[a][b]=cost[b][a]=cos;
        }
        for(int i=0;i<n;i++)
        {
            dv[i]=cv[i]=maxInt;
            visited[i]=false;
            pre[i]=-1;
        }
        dv[s]=0;
        cv[s]=0;
        while(true)
        {
            int index=findMin(n);
            if(index==-1)
                break;
            visited[index]=true;
            for(int i=0;i<n;i++)
            {
                if(map[index][i]!=maxInt&&!visited[i])
                {
                    if(dv[i]>dv[index]+map[i][index])
                    {
                        dv[i]=dv[index]+map[i][index];
                        cv[i]=cv[index]+cost[i][index];
                        pre[i]=index;
                    }
                    else if(dv[i]==dv[index]+map[i][index]&&cv[i]>cv[index]+cost[i][index])
                    {
                        dv[i]=dv[index]+map[i][index];
                        cv[i]=cv[index]+cost[i][index];
                        pre[i]=index;
                    }
                }
            }
        }
           int index=d;
        while(index!=-1)
        {
            path.push(index);
            index=pre[index];
        }
        int top;
        while(!path.empty())
        {
            top=path.top();
            printf("%d ",top);
            //cout<<top<<" ";
            path.pop();
        }
        printf("%d ",dv[d]);
        printf("%d
",cv[d]);
    }
    return 0;
}