题意：
求点1到点n的最短路，每条路可能有两种权值，如果之前访问过某个点c则权值为p,否则为r。
思路：
将之前访问过的点序列状态压缩+深搜。其实也可以不用状态压缩，当判断是否访问过c时判断cnt[c]>0就可以了。
代码：
//poj 3411
//sepNINE
#include <iostream>
using namespace std;
const int maxN=16;
int head[maxN],cnt[maxN];
struct Edge
{int v,c,p,r,next;
}edge[maxN];
int e,n,m,ans;
void dfs(int cur,int tot,int state)
{int i;if(tot>ans)return ;if(cur==n){ans=min(ans,tot);return ;} for(i=head[cur];i!=-1;i=edge[i].next){int v=edge[i].v,c=edge[i].c;if(cnt[v]>3)continue;++cnt[v]; if(state&(1<<c))dfs(v,tot+edge[i].p,state|(1<<v));elsedfs(v,tot+edge[i].r,state|(1<<v));--cnt[v];}
}int main()
{while(scanf("%d%d",&n,&m)==2){e=0;memset(head,-1,sizeof(head)); memset(cnt,0,sizeof(cnt));for(int i=0;i<m;++i){int a,b,c,p,r;scanf("%d%d%d%d%d",&a,&b,&c,&p,&r);edge[e].v=b;edge[e].c=c;edge[e].p=p,edge[e].r=r;edge[e].next=head[a];head[a]=e++;}ans=INT_MAX;dfs(1,0,0);if(ans==INT_MAX)printf("impossible\n");else printf("%d\n",ans); }return 0;
}