#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int fac[12];
int n, m;
struct node{
	int to, cost1, cost2, need, next;
}path[120];
int npath;
int first[11];

struct qnode{
	int p, s, d;
	qnode(){}
	qnode(int p, int s, int d):p(p), s(s), d(d){}
	bool friend operator < (qnode &a, qnode &b){
		return a.d<b.d;
	}
}queue[10000];
int size;
void push(qnode a){
	int i=++size;
	for(; i>1 && a<queue[i>>1]; i>>=1)
	queue[i]=queue[i>>1];
	queue[i]=a;
}
qnode pop(){
	qnode min=queue[1], last=queue[size--];
	int i=1, child;
	for(; (i<<1)<=size; i=child){
		child=i<<1;
		if(child!=size && queue[child+1]<queue[child]) child++;
		if(last<queue[child]) break;
		queue[i]=queue[child];
	}
	queue[i]=last;
	return min;
}

int dist[11][1024];
int dijkstra()
{
	int u, v, d, s;
	qnode tmp;
	memset(dist, -1, sizeof(dist));
	size=0;
	push(qnode(1, 1, 0));
	while(size>0){
		tmp=pop();
		u=tmp.p; d=tmp.d; s=tmp.s;
		if(dist[u][s]!=-1) continue;
		if(u==n) return d;
		dist[u][s]=d;
		for(int i=first[u]; i!=-1; i=path[i].next){
			v=path[i].to;
			if(dist[v][s|fac[v]]!=-1) continue;
			if(s&fac[path[i].need]) push(qnode(v, s|fac[v], d+path[i].cost1));
			else push(qnode(v, s|fac[v], d+path[i].cost2));
		}
	}
	return -1;
}
void init(){
	fac[1]=1;
	for(int i=2; i<=10; i++)
	fac[i]=2*fac[i-1];
}
int main(){
	init();
	int a;
	npath=0;
	memset(first, -1, sizeof(first));
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d %d %d", &a, &path[npath].to, &path[npath].need, &path[npath].cost1, &path[npath].cost2);
		path[npath].next=first[a];
		first[a]=npath++;
	}
	a=dijkstra();
	if(a==-1) printf("impossible\n");
	else printf("%d\n", a);
	return 0;
}

• Re:dijkstra 求最短路 (1940) 1013101127 2012-06-29 11:29:44