zoj2792.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

int n,m,p,a,b,ss;
int t[10];

int ev[2048];
int ew[2048];
int next[2048], num;
int nbs[32];

bool input(){
	scanf("%d %d %d %d %d",&n,&m,&p,&a,&b);
	if (n==0&&m==0&&p==0&&a==0&&b==0) return 0;
	int i;
	for (i=0;i<n;++i) {scanf("%d",t+i); t[i] = 2520/t[i];}
	for (i=1;i<=m;++i) nbs[i] = 0; num = 0;
	int x,y,z;
	for (i=0;i<p;++i){
		scanf("%d %d %d",&x,&y,&z);
		next[++num] = nbs[x]; nbs[x] = num; ev[num] = y; ew[num] = z;
		next[++num] = nbs[y]; nbs[y] = num; ev[num] = x; ew[num] = z;
	}
	return 1;
}

struct elem{
	int y,st;
	elem(const int &yy=0,const int &ss=0):y(yy),st(ss){}
};

int d[32][8192];
bool vst[32][8192];
elem heap[8192];
int len;
int ps[32][8192];

void update(elem r){
    int q = ps[r.y][r.st], p = q >> 1;
    while (p && d[heap[p].y][heap[p].st] > d[r.y][r.st]){
        ps[heap[p].y][heap[p].st] = q;
        heap[q] = heap[p];
        q = p; p = q >> 1;
    }
    heap[q] = r; ps[r.y][r.st] = q;
}

elem getmin(){
    elem ret = heap[1];
    int p = 1, q = 2; elem r = heap[len--];
    while (q <= len){
        if (q < len && d[heap[q+1].y][heap[q+1].st] < d[heap[q].y][heap[q].st]) q++;
        if (d[heap[q].y][heap[q].st] < d[r.y][r.st]){
            ps[heap[q].y][heap[q].st] = p;
            heap[p] = heap[q];
            p = q; q = p << 1;
        } else break;
    }
    heap[p] = r; ps[r.y][r.st] = p;
    return ret;
}

bool dij(int &ans){
    len = 1; heap[1] = elem(a, 0);
	elem tmp;
	int cx,cs,tx,ts,i,j;
	for (i=1;i<=m;++i)
		for (j=0;j<(1<<n);++j)
		{
			d[i][j]=0x3fffffff;
			vst[i][j]=0;
			ps[i][j] = 0;
		}
	d[a][0]=0;	
	ps[a][0] = 1;
	
	int v;
	while (1)
	{
        if (len == 0) return 0;
		tmp=getmin();
		cx=tmp.y;
		cs=tmp.st;
		if (cx==b)
		{
			ans=d[cx][cs];
			return 1;
		}
			vst[cx][cs]=1;
			for (i=0;i<n;++i) if ((cs&(1<<i))==0)
			{
				ts=cs|(1<<i);
				for (j=nbs[cx];j != 0;j = next[j]){
                    v = ev[j];
					if (!vst[v][ts]&&(d[cx][cs]+ew[j]*t[i])<d[v][ts])
					{
                        if (ps[v][ts] == 0){ heap[++len] = elem(v, ts); ps[v][ts] = len;}
						d[v][ts]=d[cx][cs]+ew[j]*t[i];
						update(elem(v, ts));
					}
                }
			}
	}
	return 0;
}

int main(){
	int ans;
	while (input()){
		if (dij(ans)) printf("%.3lf\n",ans/2520.0+1e-8);
		else puts("Impossible");
	}
	return 0;
}