首页 > 代码库 > 蓝桥杯 最短路 道路和航路 SPFA算法

蓝桥杯 最短路 道路和航路 SPFA算法

1.SPFA算法

  算法训练 最短路  
时间限制:1.0s   内存限制:256.0MB
      
锦囊1
使用最短路算法。
锦囊2

使用Dijkstra算法,此图的边数比点数的平方要少很多,因此应该使用带堆优化的Dijkstra。

问题描述

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入格式

第一行两个整数n, m。

接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

输出格式
共n-1行,第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定

对于10%的数据,n = 2,m = 2。

对于30%的数据,n <= 5,m <= 10。

对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。


很多时候,给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。简洁起见,我们约定加权有向图G不存在负权回路,即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。定理: 只要最短路径存在,上述SPFA算法必定能求出最小值


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int inf = 1<<30;
const int L = 200000;
struct Edges
{
    int x,y,w,next;
} e[L<<2];
int head[L];
int dis[L];
int vis[L];
int cnt[L];
void AddEdge(int x,int y,int w,int k)
{
    e[k].x = x,e[k].y = y,e[k].w = w,e[k].next = head[x],head[x] = k;
}
int relax(int u,int v,int c)
{
    if(dis[v]>dis[u]+c)
    {
        dis[v] = dis[u]+c;
        return 1;
    }
    return 0;
}
int SPFA(int src)
{
    int i;
    memset(cnt,0,sizeof(cnt));
    dis[src] = 0;
    queue<int> Q;
    Q.push(src);
    vis[src] = 1;
    cnt[src]++;
    while(!Q.empty())
    {
        int u,v;
        u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(i = head[u]; i!=-1; i=e[i].next)
        {
            v = e[i].y;
            if(relax(u,v,e[i].w)==1 && !vis[v])//v节点的最短距离更新了,但不在队列中,就把该顶点加入队列中。
            {
                Q.push(v);
                vis[v] = 1;
            }
        }
    }
}
int main()
{
    int t,n,m;
    int i,j;
    scanf("%d%d",&n,&m);
    memset(e,-1,sizeof(e));
    for(i = 1; i<=n; i++)
    {
        dis[i] = inf;
        vis[i] = 0;
        head[i] = -1;
    }
    for(i = 0; i<m; i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        AddEdge(x,y,w,i);
    }
    SPFA(1);
    for(i = 2; i<=n; i++)
        printf("%d\n",dis[i]);
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1000000
#define INF  1<<30
int head[MAXN],m=0;//构造邻接表 
struct EDGE
{
 int to,next,val;
}edge[MAXN];
int d[MAXN];//到每个顶点的最短距离 
int N;//顶点的个数 
int V;//边的条数 
struct node
{
 int id;//顶点 
 int val;
 node(int id,int val):id(id),val(val){}
 bool operator <(const node &x) const
 {
  	  return val>x.val;
 }
};
void add_edge(int u,int v,int val)
{
 	 edge[m].to=v;
 	 edge[m].val=val;
 	 edge[m].next=head[u];
 	 head[u]=m++;
}
void dijkstra(int s)
{
 	 int i;
 	 for(i=1;i<=N;i++)
     d[i]=INF;
 	 d[s]=0;
 	 priority_queue<node> q;
 	 q.push(node(s,0));
 	 while(!q.empty())
 	 {
	  int u,v,val;
	  u=q.top().id;
	  val=q.top().val;
	  q.pop();
	  int i;
	  for(i=head[u];i!=-1;i=edge[i].next)
	  {
		 v=edge[i].to;
		 if(d[v]>d[u]+edge[i].val)
		   {
			  d[v]=d[u]+edge[i].val;
			  q.push(node(v,d[v]));
	       }
      }
	  }
} 

int main()
{    
	  scanf("%d%d",&N,&V); 
	  fill(head,head+N+1,-1);
	  int i;
      for(i=0;i<V;i++)
 	  {
	   int a,b,d;
	   scanf("%d%d%d",&a,&b,&d);
	   add_edge(a,b,d);
	  // add_edge(b,a,d);
	  }
	  dijkstra(1);
	  for(i=2;i<=N;i++)
	    printf("%d\n",d[i]);
	  //system("pause");
	  return 0;
}


  算法提高 道路和航路  
时间限制:1.0s   内存限制:256.0MB
      
锦囊1
使用最短路径。
锦囊2
将城镇看成结点,将公路和航路看成边,使用带堆优化的Dijkstra来求到每个城镇的最短路。
问题描述

农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇(标号为1..T),这些城镇通过R条标号为(1..R)的道路和P条标号为(1..P)的航路相连。

每一条公路i或者航路i表示成连接城镇Ai(1<=A_i<=T)和Bi(1<=Bi<=T)代价为Ci。每一条公路,Ci的范围为0<=Ci<=10,000;由于奇怪的运营策略,每一条航路的Ci可能为负的,也就是-10,000<=Ci<=10,000。

每一条公路都是双向的,正向和反向的花费是一样的,都是非负的。

每一条航路都根据输入的Ai和Bi进行从Ai->Bi的单向通行。实际上,如果现在有一条航路是从Ai到Bi的话,那么意味着肯定没有通行方案从Bi回到Ai

农夫约翰想把他那优良的牛奶从配送中心送到各个城镇,当然希望代价越小越好,你可以帮助他嘛?配送中心位于城镇S中(1<=S<=T)。

输入格式

输入的第一行包含四个用空格隔开的整数T,R,P,S。

接下来R行,描述公路信息,每行包含三个整数,分别表示Ai,Bi和Ci

接下来P行,描述航路信息,每行包含三个整数,分别表示Ai,Bi和Ci

输出格式
输出T行,分别表示从城镇S到每个城市的最小花费,如果到不了的话输出NO PATH。
样例输入
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
样例输出
NO PATH
NO PATH
5
0
-95
-100
数据规模与约定

对于20%的数据,T<=100,R<=500,P<=500;

对于30%的数据,R<=1000,R<=10000,P<=3000;

对于100%的数据,1<=T<=25000,1<=R<=50000,1<=P<=50000。

这个题也是采用SPFA的算法,代码如下:(90分  两个测试点超时)

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 200000
#define INF  1<<30
struct EDGE
{
 int to,next,dis;
}edge[MAXN];
int m=1;
int d[25000];
int head[25000];
int vis[25000];//用来判断更新过的顶点是不是已经在队列中了
void add_edge(int u,int v,int dis)//用邻接表来保存边
{
 	 edge[m].to=v;
 	 edge[m].dis=dis;
 	 edge[m].next=head[u];
 	 head[u]=m++;
} 
void SPFA(int s)//SPFA算法的模板,记住就行了
{
 	 vis[s]=1;
 	 d[s]=0;
 	 queue<int>  q;
     q.push(s);
	 int i;
	 while(!q.empty())
	 {
      int u,v;
      u=q.front();
      q.pop();
      vis[u]=0;
      for(i=head[u];i!=-1;i=edge[i].next)
          {
	       v=edge[i].to;
	       if(d[u]!=INF&&d[v]>d[u]+edge[i].dis)
	       {
              d[v]=d[u]+edge[i].dis;
              if(!vis[v])
             {
		      vis[v]=1;
		      q.push(v);
		     }
           }
	      }
     }	 
}
/*void SPFA(int s)
{
 d[s]=0;
 int q[25000000];
 q[0]=s;
 int front=0;
 int end=1;
 vis[s]=1;
 while(front<end)
 {
  int u,v;
  u=q[front];
  vis[u]=0;
  front++;
  int i;
  for(i=head[u];i!=-1;i=edge[i].next)
  {
	 v=edge[i].to;
	 if(d[u]!=INF&&d[v]>d[u]+edge[i].dis)
	 {
	  d[v]=d[u]+edge[i].dis;
	  if(!vis[v])
	     {
	  		 vis[v]=1;
	  		 q[end++]=v;
  		  } 
	 }
  }
 }
}*/
int main()
{
 	int T,R,P,S;
 	scanf("%d%d%d%d",&T,&R,&P,&S);
 	int i;
 	for(i=0;i<=T;i++)
 	   {
        head[i]=-1;
        vis[i]=0;
        d[i]=INF;
       }
       int x,y,z;
     for(i=1;i<=R;i++)
       {
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        add_edge(y,x,z);
       }
      for(i=1;i<=P;i++)
       {
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
       }
       SPFA(S);
       for(i=1;i<=T;i++)
          if(d[i]==INF)
            printf("NO PATH\n");
          else
            printf("%d\n",d[i]);
          //  system("pause");
            return 0;	
}


如果采用dijkstra  75分 5个测试点超时

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1000000
#define INF  1<<30
//int head[MAXN],m=0;//构造邻接表 
struct EDGE
{
 int to,next,val;
}edge[MAXN];
int d[25000];
int head[25000],m=1;
int vis[25000];
//int d[MAXN];//到每个顶点的最短距离 
int N;//顶点的个数 
int V;//边的条数 
struct node
{
 int id;//顶点 
 int val;
 node(int id,int val):id(id),val(val){}
 bool operator <(const node &x) const
 {
  	  return val>x.val;
 }
};
void add_edge(int u,int v,int val)
{
 	 edge[m].to=v;
 	 edge[m].val=val;
 	 edge[m].next=head[u];
 	 head[u]=m++;
}
void dijkstra(int s)
{
 	 int i;
 	 for(i=1;i<=N;i++)
     d[i]=INF;
 	 d[s]=0;
 	 priority_queue<node> q;
 	 q.push(node(s,0));
 	 while(!q.empty())
 	 {
	  int u,v,val;
	  u=q.top().id;
	  val=q.top().val;
	  q.pop();
	  int i;
	  for(i=head[u];i!=-1;i=edge[i].next)
	  {
		 v=edge[i].to;
		 if(d[v]>d[u]+edge[i].val)
		   {
			  d[v]=d[u]+edge[i].val;
			  q.push(node(v,d[v]));
	       }
      }
	  }
} 

int main()
{    
	 /* scanf("%d%d",&N,&V); 
	  fill(head,head+N+1,-1);
	  int i;
      for(i=0;i<V;i++)
 	  {
	   int a,b,d;
	   scanf("%d%d%d",&a,&b,&d);
	   add_edge(a,b,d);
	  // add_edge(b,a,d);
	  }
	  dijkstra(1);
	  for(i=2;i<=N;i++)
	    printf("%d\n",d[i]);
	  system("pause");
	  return 0;*/
	  	int T,R,P,S;
 	scanf("%d%d%d%d",&T,&R,&P,&S);
 	//scanf("%d%d",&T,&R);
 	int i;
 	for(i=0;i<=T;i++)
 	   {
        head[i]=-1;
        vis[i]=0;
        d[i]=INF;
       }
       int x,y,z;
     for(i=1;i<=R;i++)
       {
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        add_edge(y,x,z);
       }
       for(i=1;i<=P;i++)
       {
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
       }
      dijkstra(S);
       for(i=1;i<=T;i++)
          if(d[i]==INF)
            printf("NO PATH\n");
          else
            printf("%d\n",d[i]);
            //system("pause");
            return 0;	
}


2.floyd算法(计算任意两点间的最短距离)

时间复杂度为O(N^3); N为顶点的数量

核心代码

for ( int i = 0; i < 节点个数; ++i )
{
	for ( int j = 0; j < 节点个数; ++j )
	{
		for ( int k = 0; k < 节点个数; ++k )
		{
			if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
			{
				// 找到更短路径
				Dis[i][j] = Dis[i][k] + Dis[k][j];
			}
		}
	}
}

应用的例子如下

Cow Contest

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ NA ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

输入
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

There are multi test cases.The input is terminated by two zeros.The number of test cases is no more than 20.
输出
For every case:
* Line 1: A single integer representing the number of cows whose ranks can be determined
样例输入
5 5
4 3
4 2
3 2
1 2
2 5
0 0




#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
#define MAX 0x7fffffff
const int N=110;
int dis[N][N];
int n,m;
void floyd(){
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(dis[i][k]!=MAX&&dis[k][j]!=MAX&&dis[i][j]>dis[i][k]+dis[k][j]){
				  dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}
}
int main(){
	//freopen("1.txt","r",stdin);
	while(~scanf("%d%d",&n,&m)&&n&&m){
		for(int i=1;i<=n;++i){
		  for(int j=1;j<=n;++j)
			  dis[i][j]=MAX;
		}
	  int x,y;
	  while(m--){
	   scanf("%d%d",&x,&y);
	   dis[x][y]=1;
	  }
	  floyd();
	  int ans=0;
	  for(int i=1;i<=n;++i){
		  for(int j=1;j<=n;++j){
			if(j==i)continue;
		    if(dis[i][j]==MAX&&dis[j][i]==MAX)
			{ans++;break;}
		  }
	  }
	  printf("%d\n",n-ans);
	}
  return 0;
}