蓝桥杯 ALGO-307 VIP试题 SPFA （试题解析）_综合

试题算法训练 SPFA

提交此题评测记录

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　SPFA

输入格式

　　第一行输入n,m；第二行输入begin,end

　　接下来m行输入x,y,z;

　　n表示点数，m表示边数，begin表示起始点，end表示目标点，x、y表示连同连点z表示权值

输出格式

　　输出begin到end的最短路

样例输入

7 12
1 7
1 7 10
1 2 1
1 3 2
2 7 8
2 3 1
2 4 4
2 5 1
2 6 10
3 4 3
5 6 1
5 4 7
6 7 1

样例输出

数据规模和约定

　　n,m<10^6

解题思路：SPFA算法解题。

代码如下：

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;struct Edge{int from,to;int W;Edge(int ff,int tt,int ww):from(ff),to(tt),W(ww){    }Edge(){    }
};vector< vector<Edge> >    G(1000006);
int n,m;
int Begin,End;int inq[1000006];
int d[1000006];void Read(){cin>>n>>m;cin>>Begin>>End;for(int i=1;i<=n;i++){d[i]=8888;}for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;G[x].push_back(Edge(x,y,z));G[y].push_back(Edge(y,x,z));}memset(inq,0,sizeof(inq));}void SPFA(int Beg){queue<int>    Q;Q.push(Beg);d[Beg]=0;inq[Beg]=1;while(!Q.empty()){int now=Q.front();Q.pop();inq[now]=0;int to;for(int i=0;i<G[now].size();i++){to=G[now][i].to;if(d[to]>d[now]+G[now][i].W ){d[to]=d[now]+G[now][i].W;if( inq[to]==1 )continue;inq[to]=1;Q.push(to);}}}    cout<<d[End]<<endl;}int main(int argc, char** argv) {Read();SPFA(Begin);//    cout<<"hello world!"<<endl;return 0;
}

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;

struct Edge{
   int from,to;
   int W;
   Edge(int ff,int tt,int ww):from(ff),to(tt),W(ww){   }
   Edge(){   }
};

vector< vector<Edge> > G(1000006);
int n,m;
int Begin,End;

int inq[1000006];
int d[1000006];

void Read(){
   cin>>n>>m;
   cin>>Begin>>End;

   for(int i=1;i<=n;i++){
       d[i]=8888;
   }

   for(int i=0;i<m;i++){
       int x,y,z;
       cin>>x>>y>>z;
       G[x].push_back(Edge(x,y,z));
       G[y].push_back(Edge(y,x,z));
   }


   memset(inq,0,sizeof(inq));

}

void SPFA(int Beg){
   queue<int>   Q;
   Q.push(Beg);
   d[Beg]=0;
   inq[Beg]=1;

   while(!Q.empty()){
       int now=Q.front();
       Q.pop();
       inq[now]=0;

       int to;
       for(int i=0;i<G[now].size();i++){
           to=G[now][i].to;
           if(d[to]>d[now]+G[now][i].W ){
               d[to]=d[now]+G[now][i].W;


               if( inq[to]==1 )
                   continue;

               inq[to]=1;
               Q.push(to);
           }
       }

   }

cout<<d[End]<<endl;

}

int main(int argc, char** argv) {
   Read();
   SPFA(Begin);

//   cout<<"hello world!"<<endl;
   return 0;
}

蓝桥杯 ALGO-307 VIP试题 SPFA （试题解析）

试题 算法训练 SPFA

试题算法训练 SPFA