浪里个浪（spfa最短路径）

「爱情、让人受尽委屈。」 2022-06-09 03:23 133阅读 0赞

TonyY是一个喜欢到处浪的男人，他的梦想是带着兰兰姐姐浪遍天朝的各个角落，不过在此之前，他需要做好规划。

现在他的手上有一份天朝地图，上面有n个城市，m条交通路径，每条交通路径都是单行道。他已经预先规划好了一些点作为旅游的起点和终点，他想选择其中一个起点和一个终点，并找出从起点到终点的一条路线亲身体验浪的过程。但是他时间有限，所以想选择耗时最小的，你能告诉他最小的耗时是多少吗？

Input

包含多组测试数据。

输入第一行包括两个整数n和m，表示有n个地点，m条可行路径。点的编号为1 - n。

接下来m行每行包括三个整数i, j, cost，表示从地点i到地点j需要耗时cost。

接下来一行第一个数为S，表示可能的起点数，之后S个数，表示可能的起点。

接下来一行第一个数为E，表示可能的终点数，之后E个数，表示可能的终点。

0<S, E≤n≤100000，0<m≤100000，0<cost≤100。

Output

输出他需要的最短耗时。

Sample Input

4 4
    1 3 1
    1 4 2
    2 3 3
    2 4 4
    2 1 2
    2 3 4

Sample Output

以每个起点进行一遍spfa，然后找出到终点距离最小的，然后把所有的起点和终点情况枚举完，找出最小值就可以了

#include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    #define N 101000
    #define ll long long
    using namespace std;
    int n,m,a,b,c;
    int head[N],len,vis[N],dis[N],s[N],e[N];
    struct node
    {
    	int u,v,w,next;
    } G[N];
    void add_edge(int u,int v,int w)
    {
    	G[len].v=v;
    	G[len].w=w;
    	G[len].next=head[u];
    	head[u]=len++;
    }
    void spfa(int st)
    {
    	for(int i=1; i<=n; i++)
    	{
    		dis[i]=inf;
    		vis[i]=0;
    	}
    	dis[st]=0;
    	vis[st]=1;
    	queue<int>q;
    	q.push(st);
    	while(!q.empty())
    	{
    		st=q.front();
    		q.pop();
    		//printf("%d ",st);
    		for(int i=head[st]; i!=-1; i=G[i].next)
    		{
    			int v=G[i].v,w=G[i].w;
    			//printf("%d ",v);
    			if(dis[v]>dis[st]+w)
    			{
    				dis[v]=dis[st]+w;
    				if(!vis[v])
    				{
    					vis[v]=1;
    					q.push(v);
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	while(~scanf("%d%d",&n,&m))
    	{
    		int minn=inf;
    		len=1;
    		memset(head,-1,sizeof(head));
    		for(int i=1; i<=m; i++)
    		{
    			scanf("%d%d%d",&a,&b,&c);
    			add_edge(a,b,c);
    		}
    		int x,y;
    		scanf("%d",&x);
    		for(int i=1; i<=x; i++)
    			scanf("%d",&s[i]);
    		scanf("%d",&y);
    		for(int i=1; i<=y; i++)
    			scanf("%d",&e[i]);
    		for(int i=1; i<=x; i++)
    		{
    			spfa(s[i]);
    			for(int j=1; j<=y; j++)
    				minn=min(minn,dis[e[j]]);
    		}
    		printf("%d\n",minn);
    	}
    	return 0;
    }

多源最短路问题的重点： 将所有的起点全部通过一个自己添加的初始点（比如 ‘0’点） 且0点到所有的起点的距离全部为0，然后通过一遍SPFA求出从新起点到所有点的最短路，所有点的最短距离全部找到了，最后只需要做一遍比较就好了

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    struct node
    {
        int id;
        int wi;
    } h;
    int ed;
    int dist[100100];//储存从起始点到每个点的距离
    int vis[100100];//访问变量
    int n,m,s,e;
    vector<node>v[200100];
    void spfa()
    {
        memset(vis,0,sizeof(vis));
        for(int i=0; i<=n+1; i++) dist[i]=inf;//初始距离数组为无穷大
        dist[0]=0;
        queue<int>q;
        vis[0]=1;
        q.push(0);
        while(!q.empty())
        {
            int x=q.front();//vis[x]=0;这个最好清除
            q.pop();
            for(int i=0; i<v[x].size(); i++)
            {
                int id=v[x][i].id;
                int wi=v[x][i].wi;
                if(dist[id]>dist[x]+wi)
                {
                    dist[id]=dist[x]+wi;
                }
                if(!vis[id])
                {
                    q.push(id);
                    vis[id]=1;
                }
            }
        }
    }
    int main ()
    {
        int i;
        int x,y,z;
        while(~scanf("%d %d",&n,&m))
        {
            for(i=0; i<m; i++)
                v[i].clear();
            for(i=0; i<m; i++)
            {
                scanf("%d %d %d",&x,&y,&z);
                h.id=y;
                h.wi=z;
                v[x].push_back(h);
            }
            scanf("%d",&s);
            for(i=0; i<s; i++)
            {
                scanf("%d",&x);
                h.id=x;
                h.wi=0;
                v[0].push_back(h);
            }
            spfa();
            scanf("%d",&e);
            int min=inf;
            for(i=0; i<e; i++)
            {
                scanf("%d",&ed);
                if(min>dist[ed])
                {
                    min=dist[ed];
                }
            }
            cout<<min<<endl;
        }
    }

新建一个点作为炒鸡原点，连入各个起点，再建一个炒鸡汇点，让各个终点连入这个汇点。

建好图之后，拿炒鸡原点作为起点，跑最短路即可。

\#include<stdio.h>  
\#include<string.h>  
\#include<queue>  
using namespace std;  
struct node  
\{  
    int from;  
    int to;  
    int w;  
    int next;  
\}e\[550000\];  
int head\[150000\];  
int dist\[150000\];  
int vis\[150000\];  
int n,m,cont;  
void add(int from,int to,int w)  
\{  
    e\[cont\].to=to;  
    e\[cont\].w=w;  
    e\[cont\].next=head\[from\];  
    head\[from\]=cont++;  
\}  
void SPFA()  
\{  
    memset(vis,0,sizeof(vis));  
    for(int i=0;i<=n+1;i++)dist\[i\]=0x3f3f3f3f;  
    dist\[0\]=0;  
    queue<int >s;  
    s.push(0);  
    vis\[0\]=1;  
    while(!s.empty())  
    \{  
        int u=s.front();  
        vis\[u\]=0;  
        s.pop();  
        for(int i=head\[u\];i!=-1;i=e\[i\].next)  
        \{  
            int v=e\[i\].to;  
            int w=e\[i\].w;  
            if(dist\[v\]>dist\[u\]+w)  
            \{  
                dist\[v\]=dist\[u\]+w;  
                if(vis\[v\]==0)  
                \{  
                    s.push(v);  
                    vis\[v\]=1;  
                \}  
            \}  
        \}  
    \}  
    printf("%d\\n",dist\[n+1\]);  
\}  
int main()  
\{  
    while(~scanf("%d%d",&n,&m))  
    \{  
        cont=0;  
        memset(head,-1,sizeof(head));  
        for(int i=0;i<m;i++)  
        \{  
            int x,y,w;  
            scanf("%d%d%d",&x,&y,&w);  
            add(x,y,w);  
        \}  
        int q;  
        scanf("%d",&q);  
        while(q--)  
        \{  
            int x;  
            scanf("%d",&x);  
            add(0,x,0);  
        \}  
        scanf("%d",&q);  
        while(q--)  
        \{  
            int x;  
            scanf("%d",&x);  
            add(x,n+1,0);  
        \}  
        SPFA();  
    \}  
    return 0;  
\}