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

## 边集数组...开到200200 就正好= =大小要么RE 要么TLE

Posted by dong_123 at 2013-03-14 16:03:16 on Problem 2449
```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 2000000000
#define maxn 1005
#define maxm 100100
using namespace std;
typedef struct{
int y,next,w;
}node;
struct data{
int v,d,h;
bool operator <( data a )const
{    return a.d+a.h<d+h;   }
};
node g[maxm*2];
int m,n,tot=0,kth,s,t;
int d[maxn],a[maxn],time[maxn],v[maxn],b[maxn];
g[++tot].y=y;g[tot].w=z;g[tot].next=a[x];a[x]=tot;
g[++tot].y=x;g[tot].w=z;g[tot].next=b[y];b[y]=tot;
}
void Init(){
int x,y,z;
freopen("test.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
}
scanf("%d %d %d",&s,&t,&kth);
if(s==t) kth++;
}
void Dij(){
int mind,mini,now;
for(int i=1;i<=n;i++) d[i]=inf;
memset(v,0,sizeof(v));
d[t]=0;
for(int i=1;i<=n;i++){
mind=inf;
for(int j=1;j<=n;j++)
if(!v[j]&&mind>d[j]){
mind=d[j];
mini=j;
}
v[mini]=1;
for(int s=b[mini];s;s=g[s].next){
now=g[s].y;
if(!v[now]&&d[now]>d[mini]+g[s].w){
d[now]=d[mini]+g[s].w;
}
}
}
//for(int i=1;i<=n;i++) printf("%d\n",d[i]);
}
int A_Star(){
data st,now,k;
priority_queue<data>que;
memset(time,0,sizeof(time));
st.v=s;
st.d=0;
st.h=d[s];
que.push(st);
while(!que.empty()){
k=que.top();
que.pop();
if(++time[k.v]>kth) continue;
if(time[t]==kth) return(k.d);
for(int s=a[k.v];s;s=g[s].next){
now.v=g[s].y;
now.d=k.d+g[s].w;
now.h=d[g[s].y];
que.push(now);
}
}
return(-1);
}
int main(){
Init();
Dij();
printf("%d\n",A_Star());
}```

Followed by: