hdu 1535 Invitation Cards(有向圖的來回最短路，要反向建圖)

題目：

鏈接：點擊打開鏈接

題意：

給一個圖，求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);  
                }  
            }  
        }  
    }  
}


-----------------------------------------------------------

戰斗，從不退縮；奮斗，永不停歇~~~~~~~~~~