首页 > 代码库 > POJ 3411 Paid Roads(dfs)

POJ 3411 Paid Roads(dfs)

*注:这一题很重要的是对与数据的处理和细节的把握把!


http://poj.org/problem?id=3411

题目大意:

      有n个城市,m条路,(0<=n,m<=10)。从a到b,如果之前已经经过c点,那么付费p,否者付费r。求最小的费用,从1-->n!


    注意: There may be more than one road connecting one city with another.

    so:你不能用map[a][b]存a->b的距离。只能有road [ i ]了。


   还有就是,题目没有说,每个城市只能访问一次哦,就比如样例。对于数据的读入,怎么记录a b c p r,这都要思考,还是壮哉我的结构体。

源代码:


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define maxn 100001

using namespace std;

int n,m;
int ans;
int ok;
int vis[20];
struct node{
    int a,b,c;
    int p,r;

}road[20];

void dfs(int cur,int pay)
{
    if(cur==n)
    {
        ok=1;
        if(ans>pay)
            ans=pay;
        return;
    }
    for(int i=0;i<m;i++)
    {
        if(road[i].a==cur&&vis[road[i].b]<=4)   //这里值得思考了.应为n==10,所以最多形成<=4个环,也就是每个城市最多访问4次。
        {
            int t=pay;
            vis[road[i].b]++;

            if(!vis[road[i].c])
                pay+=road[i].r;
            else
                pay+=road[i].p;
            //cout<<"--->"<<pay<<endl;
            dfs(road[i].b,pay);
            pay=t;                           //回溯
            vis[road[i].b]--;                //同上,就是所谓的dfs复原。

        }
    }
}


int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ok=0;
        ans=INF;
        memset(vis,0,sizeof vis);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d%d",&road[i].a,&road[i].b,&road[i].c,&road[i].p,&road[i].r);
        }

        vis[1]=1;
        dfs(1,0);
        if(ok)
           printf("%d\n",ans);
        else
            printf("impossible\n");




    }

    return 0;
}