POJ 3411 Paid Roads 搜索的小技巧

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

如下例：

4 4

1 2 1 10 10

2 3 2 10 10

3 1 3 10 10

2 4 3 10 90

显然花费最小的路为 1 > 2 > 3 > 1 > 2 > 4。

即花费最小的路中可能存在环，也就是说在最优路中，可能会经过某个点很多次。

因为 n <= 10,所以任意一点最多会存在于不同的四个环中，换言之，每个点最多只会走过四次，我们成这个次数为”闸数“。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

#define LL long long
#define ULL unsigned long long
#define PI (acos(-1.0))
#define EPS (1e-10)
#pragma comment(linker,"/STACK:102400000,1024000")

using namespace std;

struct N
{
    int a,b,c,p,r,next;
}edge[12];

int head[11];

int Top;

void Link(int a,int b,int c,int p,int r)
{
    edge[Top].a = a;
    edge[Top].b = b;
    edge[Top].c = c;
    edge[Top].p = p;
    edge[Top].r = r;
    edge[Top].next = head[a];
    head[a] = Top++;
}

bool me[11][11][2];
int mp[11];
int rv[11];

int dis[11];

int MAXN,Min;

void dfs(int s,int dis)
{
    if(dis >= Min)
        return ;
    if(s == MAXN)
    {
        Min = dis;
        return ;
    }
    mp[s]++;

    for(int p = head[s];p != -1;p = edge[p].next)
    {
        if(rv[edge[p].b] < 4)
        {
            rv[edge[p].b]++;
            if(mp[edge[p].c] != 0)
            {
                dfs(edge[p].b,dis+edge[p].p);
            }
            else if(mp[edge[p].c] == 0)
            {
                dfs(edge[p].b,dis+edge[p].r);
            }
            rv[edge[p].b]--;
        }
    }

    mp[s]--;
}

int main()
{
    int n,m,a,b,c,p,r,i;

    while(scanf("%d %d",&n,&m) != EOF)
    {
        memset(head,-1,sizeof(head));

        Top = 0;

        for(i = 0;i < m; ++i)
        {
            scanf("%d %d %d %d %d",&a,&b,&c,&p,&r);
            Link(a,b,c,p,r);
        }

        memset(mp,0,sizeof(mp));
        memset(rv,0,sizeof(rv));

        Min = 10000000;
        MAXN = n;

        dfs(1,0);

        if(Min == 10000000)
        {
            printf("impossible\n");
        }
        else
        {
            printf("%d\n",Min);
        }

    }
    return 0;
}

POJ 3411 Paid Roads 搜索的小技巧

原文：http://blog.csdn.net/zmx354/article/details/19348559