题目大意：给出一张有向图，求点1到点N的最短路，不同的是，对于每一条边，除了源点目标点和花费以外，还有额外点c，若走这条边之前到达过c点，花费会减少到另一个值P。如果最短路不存在，输出impossible。

先用floyd-warshall算法判断连通性，此时忽略额外的c和P。

然后用dijkstra算法，用d[i][S]表示在点i且经过了S集合的点的最短路，将每一个d[i][S]都看成一个点，用dijkstra算法计算。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int INF=(1<<29); struct edge { int from; int to; int sit; int dis1; int dis2; }; struct heapnode { int di; int num1; int num2; bool operator< (const heapnode j) const { return di>j.di; } }; edge e[15]; int d[15][1100]; int con[15][15]; int use[15][1100]; int m,n; void dijkstra(int s); void floyd_warshall(void); int main(void) { int i,j,u,p,ans; while(scanf("%d%d",&n,&m)==2) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { con[i][j]=(i==j)?1:0; } } for(i=1;i<=m;i++) { scanf("%d%d%d%d%d",&e[i].from,&e[i].to,&e[i].sit,&e[i].dis2,&e[i].dis1); con[e[i].from][e[i].to]=1; } floyd_warshall(); if(con[1][n]==0) { printf("impossible\n"); } else { dijkstra(1); ans=INF; u=(1<<(n-1)); p=(1<
      
        heap; p=(1<