PKU 1511 Invitation Cards
http://poj.org/problem?id=1511
重み付き有向グラフGの全ノードにノード1から一人ずつ派遣して、戻ってこさせたい。
この時、全てのノードに人を派遣して戻ってこさせるのに必要な最小のコストを求めろというような問題。
ノード1から2回ダイクストラするだけ。
vectorとか使うとTLEしたので、自分でリストを書いて実行しました。
node* G[..],rG[...];
void insert(node*&g,...);
inesrt(G[a],...);
inesrt(rG[a],...);
とかやってたので、コンパイルが通らなくてしばらく悩みました。
コンパイルに通らなくて悩んだのは結構久しぶりな気がします。
typedef struct _node{ int v,c; _node*next; }node; ll dist[1000000]; bool vis[1000000]; node ent[30000000]; int sz; node* G[10000000]; node* rG[1000000]; int getnum(){ int ret,c; while(!isdigit(c=getchar())); ret=c&15; while(isdigit(c=getchar()))ret=(ret<<3)+(ret<<1)+(c&15); return ret; } ll dij(node**g){ ll ret=0; priority_queue<pair<ll,ll> > q; memset(dist,-1,sizeof(dist)); memset(vis,0,sizeof(vis)); q.push(mp(0,0)); while(!q.empty()){ ll v=q.top().S,c=-q.top().F; q.pop(); if(vis[v])continue; vis[v]=1; dist[v]=c; ret+=c; for(const node*p=g[v];p;p=p->next){ if(vis[p->v])continue; if(dist[p->v]!=-1 && dist[p->v]<=c+p->c)continue; dist[p->v]=c+p->c; q.push(mp(-c-p->c,p->v)); } } return ret; } void insert(node*&g,int v,int c){ node*p=g; g=ent+sz++; g->next=p; g->v=v; g->c=c; } main(){ int t=getnum(); while(t--){ int p=getnum(); int q=getnum(); memset(G,0,sizeof(G)); memset(rG,0,sizeof(rG)); sz=0; int a,b,c; rep(i,q){ a=getnum()-1; b=getnum()-1; c=getnum(); insert(G[a],b,c); insert(rG[b],a,c); } printf("%lld\n",dij(G)+dij(rG)); } }