#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了 (3490) pengky 2015-10-28 18:02:40
  • Re:为什么MLE了 (9) pengky 2015-10-28 18:03:01