题意：
n个城市，要从1走到n
m条有向路，从ai到bi若经过了ci，则花费为pi，否则花费为ri
求最小花费
这题难点在于“城市与城市之间可能存在多条路径”：
1、 输入数据时可能会出现多条 从城市a到城市b的路径信息，但是费用有所差别；
2、 对于 从城市a到城市b 的同一条路径，允许重复走。
同一条路可以重复走，但可能出现无限重复走的情况，即出现环路。这样肯定不行，都死循环了
那么应该重复多少次才合理？这与m值有关。
题目的m值范围为<=10，那么当人一个城市被到达的次数若 >3次（不包括3），所走的方案必然出现了环路。这个没想到
但是标记环路是很麻烦的，所以就用到上次水果忍者里面标记vis的方法，就++或者--，不要只用0和1
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
struct lala
{
int a,b,c,p,r;
}road[15];
int ans,n,m,vis[15];
void dfs(int pos,int fee)
{
int i,tmp;
if(pos==n&&ans>fee)//要两个条件同时满足 pos=n时不一定return
{
ans=fee;
return ;
}
for(i=0;i<m;i++)
{
if(road[i].a==pos && vis[road[i].b]<=3)
{
tmp=road[i].b;
vis[tmp]++;
if(vis[road[i].c])
dfs(tmp,fee+road[i].p);//注意不要改变fee。。
else dfs(tmp,fee+road[i].r);
vis[tmp]--;
}
}
return;
}
int main()
{
int i;
while(~scanf("%d%d",&n,&m))
{
for(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);
memset(vis,0,sizeof vis);
vis[1]=1;
ans=inf;
dfs(1,0);
if(ans==inf)
printf("impossible\n");
else printf("%d\n",ans);
}
return 0;
}