第一个手写的堆heap数组开小了RE 开大了MLE
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAX=1101;
const int INF=1000000000;
int gra[MAX][MAX],n,m,h_t;
int dis[MAX],check[MAX],head[MAX],e_t;
int cnt[MAX];
struct Heap
{
	int id,f,g;
}heap[2*MAX*MAX];
struct Edge
{
	int id,next,sum;
}edge[101*MAX];

bool compar(Heap b,Heap a)
{
	if(a.g==b.g)
		return a.f<b.f;
	return a.g<b.g;
}

void getup(int p)
{
	int q=p>>1;
	Heap temp=heap[p];
	while(q&&compar(heap[q],temp))
	{
		heap[p]=heap[q];
		p=q;q=p>>1;
	}
	heap[p]=temp;
}

void getdown(int p)
{
	int q=p<<1;
	Heap temp=heap[p];
	while(q<h_t)
	{
		if(q+1<h_t&&compar(heap[q],heap[q+1]))
			q++;
		if(!compar(heap[q],temp)) break;
		heap[p]=heap[q];
		p=q;q=p<<1;
	}
	heap[p]=temp;
}

void pop()
{
	heap[1]=heap[--h_t];
	getdown(1);
}

void init()
{
	h_t=1,e_t=0;
	memset(cnt,0,sizeof(cnt));
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i)
	{
		dis[i]=INF,check[i]=0;
		for(int j=1;j<=n;++j)
			gra[i][j]=INF;
	}
}

void re_dijkstra(int t,int s)
{
	dis[t]=0;
	int i,j;
	for(i=0;i<n;++i)
	{
		int k=n+1,ex=INF;
		for(j=1;j<=n;++j)
			if(!check[j]&&ex>dis[j])
				ex=dis[j],k=j;
		if(k==n+1) break;
		check[k]=1;
		for(j=1;j<=n;++j)
			if(gra[j][k]!=INF&&!check[j]&&dis[j]>dis[k]+gra[j][k])
				dis[j]=dis[k]+gra[j][k];
	}
}

int solve(int s,int tt,int k)
{
	if(!check[s]) return -1;
	heap[1].f=0,heap[1].g=dis[s],heap[1].id=s;
	h_t++;
	while(h_t>1)
	{
		Heap t=heap[1];
		cnt[t.id]++;
		if(cnt[tt]==k) return t.f;
		if(cnt[t.id]>k) continue;
		pop();
		for(int j=head[t.id];j!=-1;j=edge[j].next)
		{
			heap[h_t].id=edge[j].id;
			heap[h_t].f=t.f+edge[j].sum;heap[h_t++].g=heap[h_t].f+dis[j];
			getup(h_t-1);
		}
	}
	return -1;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		while(m--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			edge[e_t].id=b,edge[e_t].next=head[a],edge[e_t].sum=c,head[a]=e_t++;
			gra[a][b]=c<gra[a][b]?c:gra[a][b];
		}
		int s,t,k;
		scanf("%d%d%d",&s,&t,&k);
		re_dijkstra(t,s);
		if(s==t) k++;
		printf("%d\n",solve(s,t,k));
	}
}



用STL的堆写的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int MAX=1001;
const int INF=1000000000;
int n,m;
int dis[MAX],check[MAX],head[MAX],e_t,ha[MAX];
int cnt[MAX];
struct Heap
{
	int f,g;
	short id;
};
struct Node
{
	short id;
	int next,sum;
}noe[MAX*100];

struct Edge
{
	int next,sum;
	short id;
}edge[100*MAX];

bool operator < (Heap a, Heap b)
{
	return a.g  > b.g;
}

void init()
{
	e_t=0;
	memset(cnt,0,sizeof(cnt));
	memset(head,-1,sizeof(head));
	memset(ha,-1,sizeof(ha));
	for(int i=1;i<=n;++i)
	{
		dis[i]=INF,check[i]=0;
	}
}

void re_dijkstra(int t,int s)
{
	dis[t]=0;
	int i,j;
	for(i=0;i<n;++i)
	{
		int k=n+1,ex=INF;
		for(j=1;j<=n;++j)
			if(!check[j]&&ex>dis[j])
				ex=dis[j],k=j;
		if(k==n+1) break;
		check[k]=1;
		for(j=ha[k];j!=-1;j=noe[j].next)
			if(!check[noe[j].id]&&dis[noe[j].id]>dis[k]+noe[j].sum)
				dis[noe[j].id]=dis[k]+noe[j].sum;
	}
}

int solve(int s,int tt,int k)
{
priority_queue<Heap> Q;
	if(!check[s]) return -1;Heap heap;
	heap.f=0,heap.g=dis[s],heap.id=s;
	Q.push(heap);
	while(!Q.empty())
	{
		Heap t=Q.top();
		cnt[t.id]++;
		Q.pop();
		if(cnt[tt]==k) return t.f;
		if(cnt[t.id]>k) continue;
		for(int j=head[t.id];j!=-1;j=edge[j].next)
		{
			heap.id=edge[j].id;
			heap.f=t.f+edge[j].sum;heap.g=heap.f+dis[j];
			Q.push(heap);
		}
	}
	return -1;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		while(m--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			edge[e_t].id=b,edge[e_t].next=head[a],edge[e_t].sum=c,head[a]=e_t;
			noe[e_t].id=a,noe[e_t].next=ha[b],noe[e_t].sum=c,ha[b]=e_t++;
		}
		int s,t,k;
		scanf("%d%d%d",&s,&t,&k);
		re_dijkstra(t,s);
		if(s==t) k++;
		printf("%d\n",solve(s,t,k));
	}
	return 0;
}

• Re:贴两段代码 表示纪念两段我死活不知道MLE哪的代码 求CHA。。。 (19) dong_123 2013-03-13 21:15:56