算法提高 道路和航路 SPFA 算法

时间：2023-03-09 17:57:02
算法提高 道路和航路 SPFA 算法

我简单的描述一下题目，题目中所说的有道路和航路：

1.公路是双向的，航路是单向的；

2.公路是正值，航路可正可负；

每一条公路i或者航路i表示成连接城镇Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代价为Ci;每一条公路，Ci的范围为0<=Ci<=10,000；

由于奇怪的运营策略，每一条航路的Ci可能为负的，也就是-10,000<=Ci<=10,000。

数据规模与约定

对于20%的数据，T<=100，R<=500，P<=500；

对于30%的数据，R<=1000，R<=10000，P<=3000；

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

输入格式

输入的第一行包含四个用空格隔开的整数T，R，P，S。(表示共有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
讲解：如果数据量比较少的话，很多方法都能做啦，什么Dijkstra，Bellman-ford，Floyd，都能简单的解决了，但是要想得满分，这道题目的数据量太大了，我直接套用的spfa   的模板直接过了，模板不错的，还能保存路径的；
 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<queue>

 #include<stack>

 using namespace std;

 const int MAXN = ;

 const int INF=0x7FFFFFFF;

 struct edge

 {

     int to,weight;

 };

 int T,R,P,S;

 vector<edge>adjmap[MAXN];//邻接表

 bool in_queue[MAXN];//顶点是否在队列中

 int in_sum[MAXN];//顶点入队的次数

 int dist[MAXN];//源点到各点的最短路

 int path[MAXN];//存储到达i的前一个顶点

 int nodesum;  //顶点数

 int edgesum;  //边数

 bool spfa(int source)

 {

     deque< int > dq;

     int i,j,x,to;

     for(int i = ;i<=T;i++)//初始化函数

     {

          in_sum[i]= ;

          in_queue[i]=false;

          dist[i]=INF;

          path[i]=-;

     }

     dq.push_back(source);

     in_sum[source]++;

     dist[source]=;        //到达本身的最短距离为0

     in_queue[source]= true;

     while(!dq.empty())

     {

         x = dq.front();

         dq.pop_front();

         in_queue[x]=false;

         for(int i = ;i<adjmap[x].size();i++)

         {

             to = adjmap[x][i].to;

             if((dist[x]<INF) && ( dist[to]>dist[x]+adjmap[x][i].weight) )

             {

                 dist[to] = dist[x]+adjmap[x][i].weight;

                 path[to] = x;

                 if(!in_queue[to])

                 {

                     in_queue[to] = true;

                     in_sum[to]++;

                     if(in_sum[to] == nodesum) return false;

                     if(!dq.empty())

                     {

                        if(dist[to]>dist[dq.front()])  dq.push_back(to);

                        else dq.push_front(to);

                     } else dq.push_back(to);

              }

          }

       }

     }

     return true;

 }

 void print_path(int x)

 {

     //输出最小的花费

     if(dist[x] == INF)//到不了的路径

         cout<<"NO PATH"<<endl;

     else cout<<dist[x]<<endl;

 //   下面是输出路径

 //    stack<int>s;

 //    int w = x;

 //    while(path[w]!=-1)

 //    {

 //        s.push(w);

 //        w=path[w];

 //    }

 //    //以下是经过的路径

 //    while(!s.empty())

 //    {

 //        cout<<s.top()<<" ";

 //        s.pop();

 //    }

 //    cout<<endl;

 }

 int main()

 {

     edge temp;

     int s,e,w;

     scanf("%d %d %d %d",&T,&R,&P,&S);

     for(int i = ;i<T;i++)

         adjmap[i].clear();//清空邻接表

     for(int i = ; i<=R; i++)

     {

         scanf("%d %d %d",&s,&e,&w);

         temp.to = e;

         temp.weight = w;

         adjmap[s].push_back(temp);

         temp.to = s;

         adjmap[e].push_back(temp);//  公路的是双向的，需要放入两次

     }

     for(int i = ;i<=P;i++)

     {

         scanf("%d %d %d",&s,&e,&w);

         temp.to = e;

         temp.weight = w;

         adjmap[s].push_back(temp);

     }

     if(spfa(S))

     {

         for(int i =;i<=T; i++ )

              print_path(i);

     }

    // else cout<<"图中存在负权回路"<<endl;

     return ;

 }

相关文章