学步园

转载请注明出处

经过然神指点，发现自己对超级源点（广义源点）的做法欠妥，空间太费，这次终于修正了。

题意：n个点，m条有向边，其中可以从给定的w个源点中任选一个作为起点，要求到达s号点的最短时间。

思路：

这样的题目的思路可以有两个：

1.一是设立一个超级源点（广义源点），由于题目中点的编号为1-n，因此不妨设0为超级源点，之后将w个可选源点和超级源点的距离设为0（这里要设双向），然后用超级源点为源点跑SPFA，然后d[s]就是所求的。

2.二是反向建图，由于只有一个终点，因此可以将u->v变为v->u，这样终点就变成了起点，多源点就变成多终点，一遍SPFA跑下来求那些“终点”的最小值，就OK了。

3.特别要注意这道题是有向边，好像很多人因为这个问题WA了。有需要的话也要注意一下标号的问题。

最后发现两种写法时间是一样的，内存也是一样的……

代码：

法一：超级源点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>

using namespace std;

const int MAXV=1010;
const int MAXE=20010;
const int inf=0x3f3f3f3f;

struct node
{
    int v;
    int dis;
    node *next;
}E[MAXE<<1],*G[MAXV],*head;

inline void add(int u,int v,int dis,node *G[])
{
    head->v=v;
    head->dis=dis;
    head->next=G[u];
    G[u]=head++;
}

int n,m,s,w,begin[MAXV];
int d[MAXV];
bool inq[MAXV];

void init()
{
    memset(G,0,sizeof(G));
    fill(d,d+MAXV,inf);
    memset(inq,false,sizeof(inq));
    head=E;
}

void SPFA(int s,int d[],node *G[])
{
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        inq[u]=false;
        for(node *p=G[u];p;p=p->next)
        {
            int v=p->v;
            int dis=p->dis;
            if(d[u]+dis<d[v])
            {
                d[v]=d[u]+dis;
                if(!inq[v])
                {
                    inq[v]=true;
                    Q.push(v);
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        init();
        int u,v,dis;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&dis);
            add(u,v,dis,G);
        }
        scanf("%d",&w);
        for(int i=0;i<w;i++)
        {
            scanf("%d",&begin[i]);
        }
        for(int i=0;i<w;i++)
        {
            add(begin[i],0,0,G);
            add(0,begin[i],0,G);
        }
        SPFA(0,d,G);
        if(d[s]==inf) printf("-1\n");
        else printf("%d\n",d[s]);
    }
    return 0;
}

法二：反向建图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>

using namespace std;

const int MAXV=1010;
const int MAXE=20010;
const int inf=0x3f3f3f3f;

struct node
{
    int v;
    int dis;
    node *next;
}E[MAXE<<1],*G[MAXV],*head;

inline void add(int u,int v,int dis,node *G[])
{
    head->v=v;
    head->dis=dis;
    head->next=G[u];
    G[u]=head++;
}

int n,m,s,w,begin[MAXV];
int d[MAXV];
bool inq[MAXV];

void init()
{
    memset(G,0,sizeof(G));
    fill(d,d+MAXV,inf);
    memset(inq,false,sizeof(inq));
    head=E;
}

void SPFA(int s,int d[],node *G[])
{
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        inq[u]=false;
        for(node *p=G[u];p;p=p->next)
        {
            int v=p->v;
            int dis=p->dis;
            if(d[u]+dis<d[v])
            {
                d[v]=d[u]+dis;
                if(!inq[v])
                {
                    inq[v]=true;
                    Q.push(v);
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        init();
        int u,v,dis;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&dis);
            add(v,u,dis,G);
        }
        scanf("%d",&w);
        for(int i=0;i<w;i++)
        {
            scanf("%d",&begin[i]);
        }

        SPFA(s,d,G);//反向建图时s为源点

        int Min=inf;
        for(int i=0;i<w;i++) Min=min(Min,d[begin[i]]);

        if(Min==inf) printf("-1\n");
        else printf("%d\n",Min);
    }
    return 0;
}