从2：30PM到10：30PM，做了好久啊，先用dij+heap没弄出来，后来一找题解，都是SPFA，那个用两个数组维护图的还真是很赞，，，虽然看了很久，然后用了个例子比划比划就好了。

本来自己写的邻接表TLE超时很沮丧，然后就照着题解的思路往下做了，用俩数组维护图+SPFA，开上IO挂，A了，1000ms（题目要求8000ms）

后来试了试vector果然慢得不行，意料之中

然后又回头看看自己写的邻接表，猛地发现，push_back这个写法有点2，我是从头结点遍历到尾巴，然后再在尾巴插入结点，改成用一个指针记住尾巴的位置，插完结点后，更新尾巴的位置就好了，把问题复杂度由O(n)变为O(1)

好吧，先就这样，A其他题目了，有空看看dij+heap怎么弄

这次的注释还是蛮多的

/*照题解的AC代码，这里用来保存图的link last两个数组竟然不用清空，实是不错*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; long long N,E; const long long MAXN=1000001; const long long INF=(1<<27)-1; bool visit[MAXN]; long long dis[MAXN]; long long que[MAXN]; struct eg { long long to,v,pre; }link[2][MAXN]; long long last[2][MAXN]; inline void SPFA(long long kind)//0是正向，1是负向 { //memset(dis,INF,sizeof(long long)*(N+1); memset(visit,0,sizeof(bool)*(N+1)); //fill(dis+1,dis+N+1,INF); for(long long i=1;i<=N;i++) { dis[i]=(1<<31)-1; } long long start=0; long long end=1; que[0]=1; dis[1]=0; long long nowedge; while(start
        
         dis[nowvert]+link[kind][nowedge].v) { if(!visit[to]) { que[end++]=to; visit[to]=true; } dis[to]=dis[nowvert]+link[kind][nowedge].v; } nowedge=link[kind][nowedge].pre;//这里要记得按链条转移nowedge哦 } } } inline long long Scan() //输入外挂 { long long res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } inline void Out(long long a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif long long T; //scanf("%lld",&T); T=Scan(); while(T--) { //scanf("%lld%lld",&N,&E); N=Scan(); E=Scan(); memset(last,-1,sizeof(last)); for(long long i=1;i<=E;i++)//建图部分 { long long a,b,v; //scanf("%lld%lld%lld",&a,&b,&v); a=Scan(); b=Scan(); v=Scan(); link[0][i].to=b; link[0][i].v=v; link[0][i].pre=last[0][a];//last点记录着加入当前边之前的从a点出来的最后一条边的编号，作为这条边的前驱 last[0][a]=i;//相应的，当前边就是最后一个出现的从a点出来的边，记录下这个边的序号 link[1][i].to=a; link[1][i].v=v; link[1][i].pre=last[1][b]; last[1][b]=i; } //求最短路部分 SPFA(0); long long sum=0; for(long long i=2;i<=N;i++) sum+=dis[i]; SPFA(1); for(long long i=2;i<=N;i++) sum+=dis[i]; //printf("%lld\n",sum); Out(sum); putchar('\n'); } } /*bug点： long long dis[1]=0 visit的更新 */
        
       
      
     
    
   
  

?

/*用vector，超时了，主要是点还是太多了，有差不多一百万个，虽然给了8秒，虽然用了OI挂，本地测试，也就6条边，都要0.8秒，确实不行。学长说STL适用于大概1W的，天。。。*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; struct node { long long to,v; }; long long N,E; const long long MAXN=1000001; const long long INF=(1<<27)-1; bool visit[MAXN]; long long dis[MAXN]; long long que[MAXN]; vector
         
          G[2][MAXN]; inline void SPFA(long long kind)//0是正向，1是负向 { //memset(dis,INF,sizeof(long long)*(N+1); memset(visit,0,sizeof(bool)*(N+1)); //fill(dis+1,dis+N+1,INF); for(long long i=1;i<=N;i++) { dis[i]=(1<<31)-1; } long long start=0; long long end=1; que[0]=1; dis[1]=0; while(start
          
           dis[nowvert]+G[kind][nowvert][i].v) { if(!visit[to]) { que[end++]=to; visit[to]=true; } dis[to]=dis[nowvert]+G[kind][nowvert][i].v; } } } } inline long long Scan() //输入外挂 { long long res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } inline void Out(long long a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif long long T; //scanf("%lld",&T); T=Scan(); while(T--) { //scanf("%lld%lld",&N,&E); N=Scan(); E=Scan(); struct node z,f; for(long long i=1;i<=E;i++)//建图部分 { long long a,b,v; //scanf("%lld%lld%lld",&a,&b,&v); a=Scan(); b=Scan(); v=Scan(); z.to=b;z.v=v; f.to=a;f.v=v; G[0][a].push_back(z); G[1][b].push_back(f); } //求最短路部分 SPFA(0); long long sum=0; for(long long i=2;i<=N;i++) sum+=dis[i]; SPFA(1); for(long long i=2;i<=N;i++) sum+=dis[i]; //printf("%lld\n",sum); Out(sum); putchar('\n'); for(int i=0;i<2;i++) { for(int j=1;j<=N;j++) { G[i][j].clear(); } } } } 
          
         
        
       
      
     
    
   
  

?