Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
边集数组...开到200200 就正好= =大小要么RE 要么TLE#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]; void Add(int x,int y,int z){ 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); Add(x,y,z); //Add(y,x,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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator