> #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;
> }
> 

• Re:为什么MLE了 (9) pengky 2015-10-28 18:03:01