poj3411——Paid Roads

题目大意：给出N个城市m条路（有向路），两个城市之间可能连有多条路，经过一条从城市ai到bi的路i的付费方式有两种，如果之前到过城市ci则付费Pi，否则就在到达bi时付费Ri，问从城市1到城市N的最小代价

输入：N m

           第i条路的描述（共m行， a_i, b_i, c_i, P_i, R_i （1 ≤ m, N ≤ 10, 0 ≤ P_i , R_i ≤ 100, P_i ≤ R_i））

输出：最小代价（如果没有从1到N的路线则输出impossible）

分析：dfs+“闸数”技巧

           最优路径中可能会存在环，也就是说可能会访问某个节点多次。因为N<=10，所以任意一个点最多存在于四个环里，也就是最多访问4次，这个次数被称为闸数（这个数到底是几有待考察，好多结题报告都不一样，而且没有解释理由）。将bool vis[]这个标记数组改为int vis[]即可。

代码：转载自http://blog.csdn.net/lyy289065406/article/details/6689310

#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;   }