hdu1535（最短路）-白红宇

hdu1535（最短路）

阅读量：6380 次

发布时间：2019-06-23

本文共 1580 字，大约阅读时间需要 5 分钟。

题目连接：

题意：给你一个源点，让你从这里派发n个学生去其余的n-1个站点去邀请人们去CSS，然后再返回CSS，使得总的cost最小。

分析：先跑一遍spfa，求出1到其他点的最短路，再反向建图，由1出发跑一遍spfa，求出其他点到1的最短路。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 1000010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair
                  
                   using namespace std;struct edge{ int u,v,w,next; edge(){} edge(int v,int w,int next):v(v),w(w),next(next){}}e[N<<1],E[N<<1];int head[N<<1],tot;int vis[N];int n,m,s;int dis1[N],dis2[N];void init(){ FILL(vis,0);FILL(head,-1); tot=0;}void addedge(int u,int v,int w){ e[tot]=edge(v,w,head[u]); head[u]=tot++;}int spfa(int dis[]){ queue
                   
                    que; for(int i=1;i<=n;i++)dis[i]=inf; vis[1]=1;dis[1]=0; que.push(1); while(!que.empty()) { int u=que.front(); que.pop();vis[u]=0; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w) { dis[v]=w+dis[u]; if(!vis[v]) { vis[v]=1; que.push(v); } } } }}int main(){ int T,u,v,w; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); E[i].u=u;E[i].v=v;E[i].w=w; addedge(u,v,w); } spfa(dis1);init(); for(int i=1;i<=m;i++) { addedge(E[i].v,E[i].u,E[i].w); } spfa(dis2); LL ans=0; for(int i=1;i<=n;i++)ans+=dis1[i]+dis2[i]; printf("%I64d\n",ans); }}