[POI2009]Wie

题目

BZOJ
虽然是解压题但也学到了简洁的码风

做法

dijkstra)跑动规

My complete code

#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
typedef int LL;
const LL maxn=1e6+9,inf=0x3f3f3f3f,up=1<<14;
inline LL Read){
	LL x0),f1); char c=getchar);
	whilec<'0' || c>'9'){ ifc=='-') f=-1; c=getchar); }
	whilec>='0' && c<='9') x=x<<3)+x<<1)+c-'0', c=getchar);
	return x*f;
}
struct node{
	LL to,nxt,d,bit;
}dis[maxn];
LL n,num,m,p,k;
LL head[209],lu[209][up],s[209];
bool visit[209][up];
inline void AddLL u,LL v,LL t,LL bit){
	dis[++num]=node){v,head[u],t,bit}; head[u]=num;
}
#define mprx,y,z) make_pairmake_pairx,y),z)
typedef pair<LL,LL> pii;
priority_queue<pair<pii,LL>,vector<pair<pii,LL> >,greater<pair<pii,LL> > >que;
inline LL Dij){
	memsetvisit,false,sizeofvisit));
	memsetlu,inf,sizeoflu));
	lu[1][0]=0;
	que.pushmpr0,1,0));
	whileque.size)){
		LL dque.top).first.first), uque.top).first.second), bitque.top).second);
		que.pop);
		ifvisit[u][bit]) continue;
		visit[u][bit]=true; 
		ifu==n) return d;
		bit|=s[u];
		forLL i=head[u];i;i=dis[i].nxt){
			LL vdis[i].to);
			ifbit|dis[i].bit)!=bit) continue;
			iflu[v][bit]>d+dis[i].d){
				lu[v][bit]=d+dis[i].d;
				que.pushmprlu[v][bit],v,bit));
			}
		}
	}return -1;
}
int main){
	n=Read); m=Read); p=Read); k=Read);
	forLL i=1;i<=k;++i){
		LL uRead)),totRead));
		whiletot--){
			LL xRead));
			s[u]|=1<<x-1);
		}
	}
	whilem--){
		LL uRead)),vRead)),tRead)),totRead));
		LL bit0);
		whiletot--){
			LL xRead));
			bit|=1<<x-1);
		}
		Addu,v,t,bit); Addv,u,t,bit);
	}
	printf"%d",Dij));
	return 0;
}