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 C111 at 2013-08-28 19:03:44 on Problem 2449
```#include <string.h>
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,SS,T,K,e;
int D[1005],S[1005];
struct node
{
int v,w,next;
}edge[100009],revedge[100009];
int head[1009],revhead[1009];
struct Statement
{
int v,d,h;
bool operator <( Statement a )const
{    return a.d+a.h<d+h;   }
};
void init()
{
e=0;
memset(head,0xff,sizeof(head));
memset(revhead,0xff,sizeof(revhead));
}
void AddEdge(int x,int y,int w)
{
edge[e].v=y;
edge[e].w=w;
edge[e].next=head[x];
head[x]=e;
revedge[e].v = x;
revedge[e].w = w;
revedge[e].next =revhead[y];
revhead[y] = e++;
}
void Dijkstra(int s)
{
S[s]=1;
D[s]=0;

for(int i=revhead[s];i!=-1;i=revedge[i].next)
{
int v=revedge[i].v;
int w=revedge[i].w;
D[v]=w;
}

for(int i=0;i<n-1;i++)
{
int j,minn=-1,w;
for(j=1;j<=n;j++)
{
if(!S[j]&&D[j]>=0)
{
if(minn<0||minn>D[j])
{
minn=D[j];
w=j;
}
}
}
if(minn<0)break;
S[w]=1;

for(int ii=revhead[w];ii!=-1;ii=revedge[ii].next)
{

int v=revedge[ii].v;
int ww=revedge[ii].w;
if(D[v]<0||D[v]>D[w]+ww)
{
D[v]=D[w]+ww;
}

}

}
}
int Astar_Kth(int s,int e)
{
Statement cur,nxt;
priority_queue<Statement>q;
int cnt[1005];
memset( cnt,0,sizeof(cnt) );
cur.v=s;
cur.d=0;
cur.h=D[s];
q.push(cur);
while(!q.empty())
{
cur=q.top();
q.pop();
cnt[cur.v]++;
if( cnt[cur.v]>K ) continue;
if( cnt[e]==K )return cur.d;

for(int i=revhead[cur.v];i!=-1;i=revedge[i].next)
{
int v=revedge[i].v;
int w=revedge[i].w;
nxt.v=v;
nxt.d=cur.d+w;
nxt.h=D[v];
q.push(nxt);

}
}
return -1;
}
int main()
{
int x,y,w,i;
while(scanf("%d %d",&n,&m)!=EOF)
{

init();
for(i=0;i<m;i++)
{
scanf("%d %d %d",&x,&y,&w);
AddEdge(x,y,w);
}

scanf("%d %d %d",&SS,&T,&K);
if(SS==T)K++;
for(i=1;i<=n;i++)
{

D[i]=INF;
}
memset(S,0,sizeof(S));
Dijkstra(SS);

printf("%d\n",Astar_Kth(T,SS));

}
return 0;
}

```

Followed by:

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

Content:

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