Demo entry 5742893

3007

   

Submitted by anonymous on Jul 12, 2016 at 03:22
Language: C++. Code size: 2.7 kB.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int n,m,v1,v2,o,Time,Length,cnt,T,D;
int From,To;
int st[505],sd[505];
int now[505],bef[505],s[505];
bool inq[505];
queue<int>q;
struct edge
{
	int n,t,l;
	edge* next;
}mem[500005],*head[505];
void add_edge(int v1,int v2,int o,int L,int T)
{
	mem[++cnt].n=v2;mem[cnt].t=T;mem[cnt].l=L;
	mem[cnt].next=head[v1];head[v1]=mem+cnt;
	if (!o)
	{
		mem[++cnt].n=v1;mem[cnt].t=T;mem[cnt].l=L;
		mem[cnt].next=head[v2];head[v2]=mem+cnt;
	}
}
void find_time()
{
	for (int i=0;i<n;i++) now[i]=INF;
	now[From]=0;q.push(From);inq[From]=1;
	while(!q.empty())
	{
		for (edge* it=head[q.front()];it;it=it->next)
		{
			if (now[it->n]>now[q.front()]+it->t)
			{
				now[it->n]=now[q.front()]+it->t;
				bef[it->n]=q.front();
				s[it->n]=s[q.front()]+it->l;
				if (!inq[it->n]) {q.push(it->n);inq[it->n]=1;}
				continue;
			} 
			if (now[it->n]==now[q.front()]+it->t)
			{
				if (s[it->n]>s[q.front()]+it->l)
				{
					bef[it->n]=q.front();
					s[it->n]=s[q.front()]+it->l;
					if (!inq[it->n]) {q.push(it->n);inq[it->n]=1;}
				}
			}
		}
		inq[q.front()]=0;q.pop();
	}
	int tmp=bef[To];
	while(tmp!=From)
	{
		st[++st[0]]=tmp;
		tmp=bef[tmp];
	}
	T=now[To];
}
void find_dis()
{
	for (int i=0;i<n;i++) {now[i]=INF;bef[i]=0;s[i]=INF;}
	now[From]=0;q.push(From);inq[From]=1;
	while(!q.empty())
	{
		for (edge* it=head[q.front()];it;it=it->next)
		{
			if (now[it->n]>now[q.front()]+it->l)
			{
				now[it->n]=now[q.front()]+it->l;
				bef[it->n]=q.front();
				s[it->n]=s[q.front()]+1;
				if (!inq[it->n]) {q.push(it->n);inq[it->n]=1;}
				continue;
			} 
			if (now[it->n]==now[q.front()]+it->l)
			{
				if (s[it->n]>s[q.front()]+1)
				{
					bef[it->n]=q.front();
					s[it->n]=s[q.front()]+1;
					if (!inq[it->n]) {q.push(it->n);inq[it->n]=1;}
				}
			}
		}
		inq[q.front()]=0;q.pop();
	}
	int tmp=bef[To];
	while(tmp!=From)
	{
		sd[++sd[0]]=tmp;
		tmp=bef[tmp];
	}
	D=now[To];
}
int main()
{
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d%d",&v1,&v2,&o,&Length,&Time);
		add_edge(v1,v2,o,Length,Time);
	}
	scanf("%d%d",&From,&To);
	find_time();
	find_dis();
	bool flg=0;
	for (int i=sd[0];i>=0;i--)
		if (st[i]!=sd[i]){flg=1;break;}
	printf("Time = %d",T);
	if (flg)
	{
		printf(": %d",From);
		for (int i=st[0];i>=1;i--) printf(" => %d",st[i]);
		printf(" => %d\n",To);
	}
	else printf("; ");
	printf("Distance = %d",D);
	printf(": %d",From);
	for (int i=sd[0];i>=1;i--) printf(" => %d",sd[i]);
	printf(" => %d\n",To);
	return 0;
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).