Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一皮代码

Posted by ACAccepted at 2019-05-09 10:07:02 on Problem 3594
#include <queue>
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=105;
const int MAXM=2005;
const int INF=0x3f3f3f3f;
int n,m,s,t,id,MIN,MAX;

struct dij
{
	int dot,w;
	
	dij(int dot,int w):dot(dot),w(w){}
	
	bool operator < (const dij tmp) const
	{
		return w>tmp.w;
	}
};

struct edge
{
	int v,w,l,r,nx;
}set[MAXM];
int head[MAXN],dis[MAXN];
bitset<MAXN> vis;
priority_queue<dij> Q;

inline void Addedge(int u,int v,int l,int r,int w)
{
	id++;set[id].v=v;set[id].w=w;set[id].l=l;set[id].r=r;set[id].nx=head[u];
	head[u]=id;
}

inline void init()
{
	int u,v,l,r,w;
	memset(head,-1,sizeof(head));
	n=read();m=read();s=read();t=read();
	for (int i=1;i<=m;i++)
	{
		u=read();v=read();l=read();r=read();w=read();
		if (r-l<w)continue;
		MIN=min(l,MIN);MAX=max(r,MAX);
		Addedge(u,v,l,r,w);
	}
}

inline int dijksta(int st)
{
	vis.reset();
	for (int i=1;i<=n;i++)dis[i]=INF+st;
	Q.push(dij(s,st));dis[s]=st;
	int u,v,w;vis.set(s);
	while (!Q.empty())
	{
		u=Q.top().dot;Q.pop();
		for (int k=head[u];k>0;k=set[k].nx)
		{
			v=set[k].v;
			w=max(dis[u],set[k].l);
			if (w+set[k].w>set[k].r)continue;
			if (w+set[k].w<dis[v])
			{
				dis[v]=w+set[k].w;
				if (!vis[v])
				{
					vis.set(v);
					Q.push(dij(v,dis[v]));
				}
			}
		}
	}
	return dis[t]-st;
}

int main()
{
	init();
	int ans=INF;
	for (int i=MIN;i<=MAX;i++) ans=min(ans,dijksta(i));
	if (ans==INF)puts("Impossible");
	else printf("%d\n",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator