題目大意：給出一張有向圖，求點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<
