水的一b。。。 20分钟就敲好了,,没想到tmd居然敢卡vector!!!纠结了,为什么用vector会超内存!!!为什么啊!!!!!!!搞的我去鸟神的blog学了个静态邻接表,用的真变扭!!!不过还好,虽蛋疼但能ac。。。。。
#include<iostream> #include<queue> #include<set> #include<algorithm> #include<vector> #include<map> #include<iomanip> #include<cmath> using namespace std; const int maxn = 1000011; const int inf = 0x3f3f3f3f; struct zz { int to; int from; int cost; int next; }zx,tz,g[maxn],g2[maxn]; int head[maxn]; int head2[maxn]; int e1,e2; int t,p,q,now,cgo,cback,temp,sum,sum2,tv; //vector<zz>g[maxn]; //vector<zz>g2[maxn]; queue<int>Q; int go[maxn]; int back[maxn]; bool vis[maxn]; inline void init() { memset(head,0,sizeof(head)); memset(head2,0,sizeof(head2)); for(int i=1;i<=p;i++) { go[i]=inf; back[i]=inf; } e1=1; e2=1; return ; } inline void add() { zx.next=head[zx.from]; head[zx.from]=e1; g[e1++]=zx; return; } inline void add2() { zx.next=head2[zx.to]; head2[zx.to]=e2; g2[e2++]=zx; return; } void spfa() { while(!Q.empty()) { Q.pop(); } memset(vis,false,sizeof(vis)); go[1]=0; Q.push(1); vis[1]=true; while(!Q.empty()) { now=Q.front(); Q.pop(); tv=head[now]; while(tv) { temp = g[tv].to; cgo = g[tv].cost + go[now]; if( cgo < go[temp] ) { go[temp]=cgo; if(!vis[temp]) { Q.push(temp); vis[temp]=true; } } tv=g[tv].next; } vis[now]=false; } sum=0; for(int x=1;x<=p;x++) { sum+=go[x]; } return ; } void spfa2() { while(!Q.empty()) { Q.pop(); } memset(vis,false,sizeof(vis)); Q.push(1); vis[1]=true; back[1]=0; while(!Q.empty()) { now=Q.front(); Q.pop(); tv=head2[now]; while(tv) { temp = g2[tv].from; cback = g2[tv].cost + back[now]; if(cback < back[temp] ) { back[temp]=cback; if(!vis[temp]) { Q.push(temp); vis[temp]=true; } } tv=g2[tv].next; } vis[now]=false; } sum2=0; for(int x=1;x<=p;x++) { sum2+=back[x]; } return ; } int main() { cin>>t; while(t--) { cin>>p>>q; init(); for(int i=1;i<=q;i++) { scanf("%d%d%d",&zx.from,&zx.to,&zx.cost); add(); add2(); } spfa(); spfa2(); printf("%d\n",sum+sum2); } return 0; }