题目链接：

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

题目：

Description

A network of m roads connects N cities (numbered from 1 toN). 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 roadi from city a_i to 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 ofa_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 cityN. 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

1：如果以前经过c城市，那么就在c城市付费。。

2：如果没有经过，那么就在b城市付费。。

还有注意题目中的数据为m<10，所以每个点最多走3次。。

因为成环的话那么最少3个点，则最少3路。所以最多走3次。。。

故应用int vis[ manx]。。。

然后dfs回溯。。。

所以代码为：

#include
  
   
#include
   
     #include
    
      #define INF 0x3f3f3f3f const int maxn=10+10; int vis[maxn]; int min_cost,fee; int n,m; struct node { int a,b,c,p,r; }e[maxn]; void dfs(int x,int fee) { if(x==n&&min_cost>fee) { min_cost=fee; return; } if(x==n) return; for(int i=1;i<=m;i++) { if(e[i].a==x&&vis[e[i].b]<3) { vis[e[i].b]++; if(vis[e[i].c]) dfs(e[i].b,fee+e[i].p); else dfs(e[i].b,fee+e[i].r); vis[e[i].b]--; } } } int main() { while(scanf("%d %d",&n,&m)!=EOF) { memset(vis,0,sizeof(vis)); min_cost=INF; for(int i=1;i<=m;i++) { scanf("%d%d%d%d%d",&e[i].a,&e[i].b,&e[i].c,&e[i].p,&e[i].r); } vis[1]=1; dfs(1,0); if(min_cost!=INF) printf("%d\n",min_cost); else printf("impossible\n"); } return 0; }