POJ 1724 - ROADS


问题描述

给定一个图,图中每条路都有 路长Length 和 过路费Toll 两个参数,一条路连接两个城市,任意两个城市之间有且仅有一条路。

现在只有 K 块钱,要求从起点City1出发,到达终点CityN的最短路,也就是说在 K 花费内的最短路。

解题思路

这个题其实有很多种解法的,只不过是题目描述用的模型是最短路的模型,其实方法多种多样,Discuss里有同学用dijkstra+A*算法,也有人用BFS+优先队列,也有人用直接用STL的priotrity_queue+剪枝…..

我用了DFS+剪枝去做:

每个城市只能到达1次,每次找满足 Toll<RestMoney 的城市;当NowLen>MinLen就回溯,无需往下搜索了;递归出口是遍历所有允许的情况。

其实这题难度不大,关键是建立 邻接链表 去存储相同Source的路径去提高搜索效率。

因为Bob每进入一个Cityk,他就只能选择以k为源点的路径走向下一个城市,此时应该直接枚举所有以k为源点的路径。若使用了其他存储方式,则必然每次都要在所有路径中重新寻找以k为源点的路径,再枚举,这相当浪费时间。

测试数据

AC 源码

解题风格一: C++

//Memory Time 
//440K   250MS 

/*--- C++ Class ---*/

#include<iostream>
using namespace std;

class Road
{
    public:
        int S,D,L,T;  //Source,Destination,Length,Toll
        int next;     //指向相同Source的下一条边
};

class info
{
    public:
        info(int N,int R)
        {
            road=new Road[R+1];
            vist=new bool[N+1];
            ListTable_Head=new int[N+1];

            memset(vist,false,sizeof(bool)*(N+1));
            memset(ListTable_Head,-1,sizeof(int)*(N+1));
            MinLen=1e7;
            pr=0;
        }
        ~info()
        {
            delete[] road;
            delete[] vist;
            delete[] ListTable_Head;
        }

        void input(int R);
        void output(void);
        void DFS(int NowCity,int NowLen,int RestMoney,int N);

    protected:
        Road* road;
        bool* vist;
        int* ListTable_Head;  //邻接链表头指针数组
        int MinLen;
        int pr;   //road[]指针
};

void info::input(int R)
{
    for(int i=1;i<=R;i++)
    {
        int s,d,l,t;
        cin>>s>>d>>l>>t;

        road[pr].S=s;
        road[pr].D=d;
        road[pr].L=l;
        road[pr].T=t;
        road[pr].next=ListTable_Head[s];
        ListTable_Head[s]=pr++;
    }
    return;
}

void info::output()
{
    cout<<(MinLen<1e7?MinLen:-1)<<endl;
    return;
}

void info::DFS(int NowCity,int NowLen,int RestMoney,int N)
{
    if(NowLen>MinLen)
        return;

    if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
    {
        MinLen=NowLen;
        return;
    }

    for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
    {
        int tD=road[i].D;
        int tL=road[i].L;
        int tT=road[i].T;

        if(!vist[tD] && RestMoney>=tT)
        {
            vist[tD]=true;
            DFS(tD,NowLen+tL,RestMoney-tT,N);
            vist[tD]=false;
        }
    }
    return;
}

int main(void)
{
    int K,N,R;  //Money,CityNum,RoadNum
    while(cin>>K>>N>>R)
    {
        info poj1724(N,R);
        poj1724.input(R);
        poj1724.DFS(1,0,K,N);
        poj1724.output();
    }
    return 0;
}

解题风格二: C

//Memory Time 
//444K   235MS 

/*--- C Style ---*/

#include<iostream>
using namespace std;

const int inf=1e7;
const int CitySize=101;
const int RoadSize=10001;

struct
{
    int S,D,L,T;  //Source,Destination,Length,Toll
    int next;     //指向相同Source的下一条边
}road[RoadSize];

int pr;   //road[]指针
int K,N,R;  //Money,CityNum,RoadNum
int MinLen;
bool vist[CitySize];
int ListTable_Head[CitySize];  //邻接链表头指针数组

void DFS(int NowCity,int NowLen,int RestMoney)
{
    if(NowLen>MinLen)
        return;

    if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
    {
        MinLen=NowLen;
        return;
    }

    for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
    {
        int tD=road[i].D;
        int tL=road[i].L;
        int tT=road[i].T;

        if(!vist[tD] && RestMoney>=tT)
        {
            vist[tD]=true;
            DFS(tD,NowLen+tL,RestMoney-tT);
            vist[tD]=false;
        }
    }
    return;
}

int main(void)
{
    while(cin>>K>>N>>R)
    {
        memset(ListTable_Head,-1,sizeof(ListTable_Head));
        memset(vist,false,sizeof(vist));
        pr=0;
        MinLen=inf;

        for(int i=1;i<=R;i++)
        {
            int s,d,l,t;
            cin>>s>>d>>l>>t;
            road[pr].S=s;
            road[pr].D=d;
            road[pr].L=l;
            road[pr].T=t;
            road[pr].next=ListTable_Head[s];
            ListTable_Head[s]=pr++;
        }

        DFS(1,0,K);

        cout<<(MinLen<inf?MinLen:-1)<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 3274 - Gold Balanced Lineup POJ 3274 - Gold Balanced Lineup
POJ 3274 - Gold Balanced Lineup Time: 2000MS Memory: 65536K 难度: 初级 分类: 高效查找法 问题描述农夫约翰的N(1≤N≤100000)头奶牛有很多相同之处。其实,约翰己经将
2011-08-11
下一篇 
POJ 1113 - Wall POJ 1113 - Wall
POJ 1113 - Wall Time: 1000MS Memory: 10000K 难度: 初级 分类: 凸包 问题描述给定多边形城堡的n个顶点,绕城堡外面建一个围墙,围住所有点,并且墙与所有点的距离至少为L,求这个墙最小的长度。
2011-08-10
  目录