Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴两段代码 表示纪念两段我死活不知道MLE哪的代码 求CHA。。。

Posted by xyh33210 at 2010-03-22 15:36:08 on Problem 2449
```第一个手写的堆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 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));
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();
{
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);
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));
}
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int MAX=1001;
const int INF=1000000000;
int n,m;
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(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;
{
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);
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;
}

```

Followed by: