双头队列+spfa的运用

本文主要是介绍双头队列+spfa的运用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

bzoj  2100 双头队列优化spfa

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
deque<int> q;
int head[100010] , to[400010] , len[400010] , next[400010] , cnt , dis[100010][2] , inq[100010] , n;
inline int read()
{int ret = 0; char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9') ret = (ret << 3) + (ret << 1) + ch - '0' , ch = getchar();return ret;
}
void add(int x , int y , int z)
{to[++cnt] = y;len[cnt] = z;next[cnt] = head[x];head[x] = cnt;
}
void spfa(int s , int p)
{int i , x;for(i = 1 ; i <= n ; i ++ )dis[i][p] = 0x3fffffff;dis[s][p] = 0;q.push_front(s);while(!q.empty()){x = q.front();q.pop_front();inq[x] = 0;for(i = head[x] ; i ; i = next[i]){if(dis[to[i]][p] > dis[x][p] + len[i]){dis[to[i]][p] = dis[x][p] + len[i];if(!inq[to[i]]){inq[to[i]] = 1;int t;if(!q.empty()) t = q.front();if(!q.empty() && dis[to[i]][p] < dis[t][p]) q.push_front(to[i]);else q.push_back(to[i]);}}}}
}
int main()
{int m , s , t1 , t2 , i , x , y , z;m = read() , n = read() , s = read() , t1 = read() , t2 = read();for(i = 1 ; i <= m ; i ++ )x = read() , y = read() , z = read() , add(x , y , z) , add(y , x , z);spfa(t1 , 0);spfa(t2 , 1);printf("%d\n" , min(dis[s][0] + dis[t2][0] , dis[s][1] + dis[t1][1]));return 0;
}

这篇关于双头队列+spfa的运用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---