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

迷之MLE,大神看一看谢谢

Posted by 5095187020216 at 2017-07-11 16:46:07 on Problem 3463
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;
int T;
int n,m,s,t;
struct node
{
	int dis,l;
	bool k;	
};
struct cmp  
{  
    bool operator()(node a,node b)  
    {   
        return a.dis>b.dis;  
    }   
}; 
int d1[1001],d2[1001];
int cnt1[1001],cnt2[1001];
bool v1[1001],v2[1001];
struct edge
{
	int to,v,next;	
}e[10001];
int edgenum=0;
int link[1001]={0};
void add(int a,int b,int v)
{
	edgenum++;
	e[edgenum].to=b;
	e[edgenum].v=v;
	e[edgenum].next=link[a];
	link[a]=edgenum;
	return;	
}
priority_queue<node,vector<node>,cmp> q;
void dijkstra()
{	
	node st;
	st.dis=0;	
	st.k=true;
	st.l=s;
	d1[s]=0;
	cnt1[s]=0;
	q.push(st);
	st.dis=0;	
	st.k=false;
	st.l=s;
	d2[s]=0;
	cnt2[s]=0;
	q.push(st);
	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(x.k)if(v1[x.l])continue;
		else if(v2[x.l])continue;//cout<<(x.k?"F":"S")<<x.l<<" "<<x.dis<<endl;
		node r;
		for(int i=link[x.l];i!=0;i=e[i].next)
		{
			if(x.dis+e[i].v<d1[e[i].to])
			{
				d2[e[i].to]=d1[e[i].to];
				cnt2[e[i].to]=cnt1[e[i].to];//cout<<e[i].to<<" "<<cnt2[e[i].to]<<"^^^^^"<<endl;
				d1[e[i].to]=x.dis+e[i].v;
				cnt1[e[i].to]=cnt1[x.l];
				r.k=true;
				r.dis=d1[e[i].to];
				r.l=e[i].to;
				q.push(r);
				r.k=false;
				r.dis=d2[e[i].to];
				r.l=e[i].to;
				q.push(r);
				continue;	
			}
			if(x.dis+e[i].v==d1[e[i].to])	
			{
				cnt1[e[i].to]++;
				r.k=true;
				r.dis=d1[e[i].to];
				r.l=e[i].to;
				q.push(r);	
				continue;
			}
			if(x.dis+e[i].v<d2[e[i].to]&&x.dis+e[i].v>d1[e[i].to])
			{
				d2[e[i].to]=x.dis+e[i].v;
				cnt2[e[i].to]=(x.k?cnt1[x.l]:cnt2[x.l]);//cout<<e[i].to<<" "<<cnt2[e[i].to]<<"^^^^^"<<endl;
				r.k=false;
				r.dis=d2[e[i].to];//cout<<r.dis<<endl;
				r.l=e[i].to;
				q.push(r);	
				continue;
			}
			if(x.dis+e[i].v==d2[e[i].to])	
			{
				cnt2[e[i].to]++;//cout<<e[i].to<<" "<<cnt2[e[i].to]<<"^^^^^"<<endl;
				r.k=false;
				r.dis=d2[e[i].to];
				r.l=e[i].to;
				q.push(r);	
				continue;
			}
		}
		if(x.k)v1[x.l]=true;
		else v2[x.l]=true;		
	}
	cnt1[s]=cnt2[s]=1;
	//for(int i=1;i<=n;i++)cout<<d1[i]<<" ";cout<<endl;
	//for(int i=1;i<=n;i++)cout<<d2[i]<<" ";cout<<endl;
	//for(int i=1;i<=n;i++)cout<<cnt1[i]<<" ";cout<<endl;
	//for(int i=1;i<=n;i++)cout<<cnt2[i]<<" ";cout<<endl;
	int res;
	if(d2[t]==d1[t]+1)res=cnt1[t]+cnt2[t];
	else res=cnt1[t];
	cout<<res<<endl;
	return;
}
int main()
{
	cin>>T;
	while(T--)
	{
		memset(d1,INF,sizeof(d1));
		memset(d2,INF,sizeof(d2));
		memset(cnt1,0,sizeof(cnt1));
		memset(cnt2,0,sizeof(cnt2));
		memset(v1,0,sizeof(v1));
		memset(v2,0,sizeof(v2));
		memset(link,0,sizeof(link));
		memset(e,0,sizeof(e));
		edgenum=0;
		scanf("%d%d",&n,&m);
		int a,b,c;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);	
		}	
		scanf("%d%d",&s,&t);
		dijkstra();
	}
	//system("pause");
	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