poj 3411 Paid Roads

　　题意：有m条路，n座城市，走这些路是要付费的，每条路由两种付费方案，设一条路两端是a，b，如果走完这条路在b点付费的话，应付r，如果走这条路之前在c点付费的话，应付p，求从1端点走到n端点的最小费用。

　　DFS

　　刚开始想到了用搜索，自己搜索学的不好，有几个问题解决不了，首先就是每个点可以走多次，不能用0，1标记一个点是否走过，如果不标记就可能在一直走一条循环路，还有就是不会回溯，总之，自己就是不会写...

　　网上抄的别人的代码，每个点最多可以走3次，回溯也挺简单...

#include<stdio.h>

#include<string.h>

int n,m;

struct node{

    int a,b,c,p,r;

};

node road[];

int visit[],mincost;

void DFS(int a,int fee)

{

    if(a==n && mincost>fee)

    {

        mincost=fee;

        return;

    }

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

    {

        if(a==road[i].a && visit[road[i].b]<=)

        {

            int b=road[i].b;

            visit[b]++;

            if(visit[road[i].c])

                DFS(b,fee+road[i].p);

            else

                DFS(b,fee+road[i].r);

            visit[b]--;

        }

    }

    return ;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(visit,,sizeof(visit));

        visit[]=;

        mincost=;

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

            scanf("%d%d%d%d%d",&road[i].a,&road[i].b,&road[i].c,&road[i].p,&road[i].r);

        DFS(,);

        if(mincost==)

            printf("impossible\n");

        else

            printf("%d\n",mincost);

    }

    return ;

}