题目：

链接：点击打开链接

题意：

给一个图，求1到各点和各点到1最短路。

思路：

先spfa,然后反向建图，在spfa就行了。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define INF 100000000 const int N = 1000010; struct node{ int u,v,w; }edge[N]; int dis[N],vis[N]; int first[N],next[N]; int p,m; void spfa1(int u) { for(int i=0; i<=p; i++) { dis[i] = INF; } dis[u] = 0; memset(vis,0,sizeof(vis)); queue
      
        q; q.push(u); while(!q.empty()) { u = q.front(); q.pop(); vis[u] = 0; for(int k=first[u]; k!=-1; k=next[k]) { int v = edge[k].v; if(dis[v] > dis[u] + edge[k].w) { dis[v] = dis[u] + edge[k].w; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } } void spfa2(int u) { for(int i=0; i<=p; i++) { dis[i] = INF; } dis[u] = 0; memset(vis,0,sizeof(vis)); queue
       
         q; q.push(u); while(!q.empty()) { u = q.front(); q.pop(); vis[u] = 0; for(int k=first[u]; k!=-1; k=next[k]) { int v = edge[k].u; if(dis[v] > dis[u] + edge[k].w) { dis[v] = dis[u] + edge[k].w; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } } void buildGraph() { memset(next,-1,sizeof(next)); memset(first,-1,sizeof(first)); for(int i=0; i
        
         >t; while(t--) { scanf("%d%d",&p,&m); memset(first,-1,sizeof(first)); memset(next,-1,sizeof(next)); for(int i=0; i
         
          
 ----------------------------------------------------------------------- 
          
 
          
收获：
 
          
->学习到了SPFA算法：
 
          
->思想：
 
          
->模板：
 
          
 
          
void add(int i,int j,int w)  
{  
    e[t].from=i;  
    e[t].to=j;  
    e[t].w=w;  
    e[t].next=head[i];  
    head[i]=t++;  
}  
void spfa(int s)  
{  
    queue 
           
             q;  
    for(int i=1;i<=n;i++)  
    dist[i]=inf;  
    memset(vis,false,sizeof(vis));  
    q.push(s);  
    dist[s]=0;  
    while(!q.empty())  
    {  
        int u=q.front();  
        q.pop();  
        vis[u]=false;  
        for(int i=head[u];i!=-1;i=e[i].next)  
        {  
            int v=e[i].to;  
            if(dist[v]>dist[u]+e[i].w)  
            {  
                dist[v]=dist[u]+e[i].w;  
                if(!vis[v])  
                {  
                    vis[v]=true;  
                    q.push(v);  
                }  
            }  
        }  
    }  
}
           
          
 ----------------------------------------------------------- 
          
 
          
战斗，从不退缩；奋斗，永不停歇~~~~~~~~~~