例题: 1129. 热浪
spfa(循环队列模拟)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
#define x fist
#define y second
const int N = 2510,M = 6200 * 2 + 10;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int q[N]; //循环队列
int t,c; //表示
int be,ed;
void add(int a,int b,int c){
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[be] = 0;
int hh = 0,tt = 1; //循环队列的写法(tt指向队首)
q[0] = be; //{节点编号}
/*
或者 int hh = 0, tt = 0;
q[tt++] = be;
*/
st[be] = true;
while(hh != tt){ //注意循环队列的判断条件
int t = q[hh++];
st[t] = false;
//枚举t节点的所有邻边,将所有可以更新的dist入队
for(int i = h[t];i != -1;i = ne[i]){
int j = e[i];
if (hh == N) hh = 0; //循环队列
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if(!st[j]){
q[tt++] = j;
if (tt == N) tt = 0; //循环队列
st[j] = true;
}
}
}
}
//因为没有出现负权边,所以可以直接==判断
if(dist[ed] > 0x3f3f3f3f / 2) return -1;
return dist[ed];
}
int main(){
memset(h,-1,sizeof h);
cin >> t >> c >> be >> ed;
for(int i = 0;i < c;++i){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c); add(b,a,c);
}
cout << spfa() << endl;
return 0;
}
喜欢看小炫是吧
忘了我吧
写错了哦,循环队列添加元素是
q[tt++] = j
,照你的写法如果用完整个数组会出错,你用同样的写法用spfa解香甜的黄油这题就会错了,这题数据更大,真正用到了循环确实是这样,谢谢指正