加载中...

POJ 3411 - Paid Roads


0x00 POJ 原题

Description

A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city a_(i) to city b_(i):

  • in advance, in a city c_(i) (which may or may not be the same as a_(i));
  • after the travel, in the city b_(i).

The payment is P_(i) in the first case and R_(i) in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

Input

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of a_(i), b_(i), c_(i), P_(i), R_(i) (1 ≤ i ≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ P_(i) , R_(i) ≤ 100, P(i) ≤ **R(i)** (1 ≤ i ≤ m).

Output

The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

Sample Input

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

Sample Output

110

Source

Northeastern Europe 2002, Western Subregion

0x10 题目概述

有 n 座城市和 m(1<=n,m<=10)条路。现在要从城市 1 到城市 n。有些路是要收费的,从 a 城市到 b 城市,如果之前到过 c 城市,那么只要付 P 的钱,如果没有去过就付 R 的钱。求的是最少要花多少钱。

注意: 注意:路径是有向的。

0x20 解题思路

DFS。这题当有了思路后,做起来是没有难度的,但是思维推算能力要求很高。

这题难点在于“城市与城市之间可能存在多条路径”:

  1. 输入数据时可能会出现多条 从城市 a 到城市 b 的路径信息,但是费用有所差别;
  2. 对于 从城市 a 到城市 b 的同一条路径,允许重复走。

有人会问,重复走同一条路径有什么意义?单纯增加费用而已,为什么不能标记所有路径,每条路只允许走一次,这样费用不是更少么?

我开始也是陷入了这种思维,但是这种想法其实“对一半,错一半”。

先来看一组数据:

6 5

1 2 1 10 10

2 3 4 10 100

2 4 2 15 15

4 1 1 12 12

3 6 6 10 10

如果每条路只允许走一次,那么方案只有 1 个:

1->2->3->6 共 135 元

但这组数据的正确答案是 67 元。为什么?正确的方案如下:

1->2->4->1->2->3->6 共 67 元

显然 1->2 重复走了一次,目的是为了先到达城市 4,从而使得 2->3 这段路的费用从 100 缩减到 10 元。

看到这里很多同学好像就恍然大悟,但是问题马上又来了。如果同一条路允许重复走,那么就不能标记了,但一旦不标记,失去了搜索的限制条件,DFS 就无法结束,不是陷入死循环了?

我刚才说这种思路“对一半,错一半”,“对”是对在“重复走会增加费用”,“错”是错在“重复走的对象不是某一条路,而是某一个环路”。在同一个环路重复走才会真正增加费用。但是标记环路是很麻烦的,那么能不能根据某一条路或某一个城市重复走过的次数来判断当前所走的方案已经出现了环路? 答案是可以的。

上述的例子已经验证过了,同一条路可以重复走,但是不能无限重复走,重复的次数是有限的。那么应该重复多少次才合理?这与 m 值有关。题目的 m 值范围为 <=10,那么当人一个城市被到达的次数若 >3 次(不包括 3),所走的方案必然出现了环路(网上的同学称之为“闸数”)。

因此只需把 bool vist[] 修改为 int vist[] 进行标记,本题就能解决了。

注:最近刚刚接触了 C++的面向对象,所以程序用 class 写了一次,用 C 风格写了一次。

0x30 测试数据

0x40 AC 源码

0x41 解题风格一:C++

//Memory Time 
//248K   0MS  

/*---- C++面向对象 ----*/

#include<iostream>
using namespace std;

class Road
{
    public:
        int a,b,c,p,r;
};

class info
{
    public:
        info():MinCost(2000)   //C++的'='和'()'都能赋值
        {                       //但构造函数这里只能用'()'
            road=new Road[11];
            vist=new int[11];
            memset(vist,0,sizeof(int)*11);
            vist[1]=1;   //从城市1出发,因此预记录到达1次
        }
        ~info()
        {
            delete[] road;
            delete[] vist;
        }

        void input(void);
        void output(void);
        void DFS(int a,int fee);

    protected:
        int n;  //城市数
        int m;  //道路数
        int MinCost;  //最小总花费
        int *vist;  //记录城市的访问次数,每个城市最多经过3次
        Road *road;  //每条道路的付费规则
};

void info::input(void)
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>road[i].a>>road[i].b>>road[i].c>>road[i].p>>road[i].r;

    return;
}

void info::output(void)
{
    if(MinCost==2000)
        cout<<"impossible"<<endl;
    else
        cout<<MinCost<<endl;

    return;
}

void info::DFS(int a,int fee)   //a:当前所在城市,fee:当前方案的费用
{
    if(a==n && MinCost>fee)
    {
        MinCost=fee;
        return;
    }

    for(int i=1;i<=m;i++)  //枚举道路
    {
        if(a==road[i].a && vist[ road[i].b ]<=3)
        {
            int b=road[i].b;
            vist[b]++;

            if(vist[ road[i].c ])
                DFS(b,fee+road[i].p);
            else
                DFS(b,fee+road[i].r);

            vist[b]--;       //回溯
        }
    }
    return;
}

int main(void)
{
    info poj3411;
    poj3411.input();
    poj3411.DFS(1,0);
    poj3411.output();
    return 0;
}

0x42 解题风格二:C

//Memory Time 
//248K  16MS 

/*---- C风格 ----*/

#include<iostream>
using namespace std;

int n;  //城市数
int m;  //道路数
int vist[11];  //记录城市的访问次数,每个城市最多经过3次
int MinCost;  //最小总花费
struct
{
    int a,b,c,p,r;
}road[11];  //每条道路的付费规则

void DFS(int a,int fee)   //a:当前所在城市,fee:当前方案的费用
{
    if(a==n && MinCost>fee)
    {
        MinCost=fee;
        return;
    }

    for(int i=1;i<=m;i++)  //枚举道路
    {
        if(a==road[i].a && vist[ road[i].b ]<=3)
        {
            int b=road[i].b;
            vist[b]++;

            if(vist[ road[i].c ])
                DFS(b,fee+road[i].p);
            else
                DFS(b,fee+road[i].r);

            vist[b]--;       //回溯
        }
    }
    return;
}

int main(void)
{
    while(cin>>n>>m)
    {
        memset(vist,0,sizeof(vist));
        vist[1]=1;    //从城市1出发,因此预记录到达1次
        MinCost=2000;

        for(int i=1;i<=m;i++)
            cin>>road[i].a>>road[i].b>>road[i].c>>road[i].p>>road[i].r;

        DFS(1,0);
        if(MinCost==2000)
            cout<<"impossible"<<endl;
        else
            cout<<MinCost<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
赏
  目录