pat天梯赛练习集合 L3-007 天梯地图

加了一些花的最短路，点的个数为500不需要堆优化，改一下dij的判断条件就可以了。

上代码：

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn=;

const int inf=0x3f3f3f3f;

struct node

{

    int id;

    int cost;

    int time;

};

int s,e;

int n,m;

vector<int> line0;

vector<int> line1;

vector<node> edge[maxn];

int d0[maxn];

int d1[maxn];

void build_map()

{

    int v1,v2,ow,cost,time;

    scanf("%d %d %d %d %d",&v1,&v2,&ow,&cost,&time);

    node temp;

    temp.cost=cost;

    temp.time=time;

    temp.id=v2;

    edge[v1].push_back(temp);

    if(ow==)

    {

        temp.id=v1;

        edge[v2].push_back(temp);

    }

}

void dij0() // deug

{

    int vis[maxn];

    int pre[maxn];

    int cost[maxn];

    cost[s]=;

    pre[s]=-;

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++) d0[i]=inf;

    d0[s]=;

    while()

    {

        int v=-;

        for(int i=;i<=n;i++)

        {

            if(vis[i]==  && ( v==- || d0[v] > d0[i])) v=i;

        }

        if(v==-) break;

        vis[v]=;

        int len=edge[v].size();

        for(int i=;i<len;i++)

        {

            node temp=edge[v][i];

            if(vis[temp.id] == )

            {

                if(d0[temp.id] > d0[v]+temp.time )

                {

                    d0[temp.id]=d0[v]+temp.time;  //

                    pre[temp.id]=v;

                    cost[temp.id]=cost[v]+temp.cost;

                }

                else  if(d0[temp.id] == d0[v]+temp.time)

                {

                    if(cost[temp.id] > cost[v]+temp.cost)

                    {

                        cost[temp.id]=cost[v]+temp.cost;

                        pre[temp.id]=v;

                    }

                }

            }

        }

    }

   // cout<<"1"<<endl;

    int zz=e;

    line0.push_back(e);

    while(pre[zz]!=-)   //

    {

        line0.push_back(pre[zz]);

        zz=pre[zz];

      //  cout<<zz<<endl;

    }

    //cout<<"2"<<endl;

    reverse(line0.begin(),line0.end());

}

void dij1() // deug

{

    int vis[maxn];

    int pre[maxn];

    int cost[maxn];

    cost[s]=;

    pre[s]=-;

    memset(vis,,sizeof(vis));

   // vis[s]=1;

    for(int i=;i<=n;i++) d1[i]=inf;

    d1[s]=;

    while()

    {

        int v=-;

        for(int i=;i<=n;i++)

        {

            if(vis[i]==  && (v==- || d1[v] > d1[i])) v=i;

        }

        if(v==-) break;

        vis[v]=;

       // line1.push_back(v);

        int len=edge[v].size();

        for(int i=;i<len;i++)

        {

            node temp=edge[v][i];

            if(vis[temp.id]==)

            {

                if(d1[temp.id] > d1[v]+temp.cost)

                {

                    d1[temp.id]=d1[v]+temp.cost;  //

                    pre[temp.id]=v;

                    cost[temp.id]=cost[v]+;

                }

                else if(d1[temp.id] == d1[v]+temp.cost)

                {

                    if(cost[temp.id] > cost[v]+)

                    {

                        cost[temp.id]=cost[v]+;

                        pre[temp.id]=v;

                    }

                }

            }

        }

    }

    int zz=e; // route

    line1.push_back(e);

    while(pre[zz]!=-)

    {

        line1.push_back(pre[zz]);

        zz=pre[zz];

    }

    reverse(line1.begin(),line1.end());

}

int check()

{

    int len1=line1.size();

    int len0=line0.size();

    if(len1 != len0) return ;

    for(int i=;i<len1;i++)

    {

        if(line0[i] != line1[i]) return ;

    }

    return -;

}

int main()

{

    cin>>n>>m;

    while(m--) build_map();

    cin>>s>>e;

    dij0();// 0 refers to the shortest time

    dij1();// 1 refers to the shortset cost

    if(check() == ) // diff

    {

        printf("Time = %d: ",d0[e]);

        cout<<line0[];

        for(int i=;i<line0.size();i++) cout<<" => "<<line0[i];

        cout<<endl;

        printf("Distance = %d: ",d1[e]);

        cout<<line1[];

        for(int i=;i<line1.size();i++) cout<<" => "<<line1[i];

        cout<<endl;

    }

    else

    {

        printf("Time = %d; ",d0[e]);

        printf("Distance = %d: ",d1[e]);

        cout<<line1[];

        for(int i=;i<line1.size();i++) cout<<" => "<<line1[i];

        cout<<endl;

    }

    return ;

}