# 求助
有点理解不了,这是我的SPFA,刚才试了下题解中的一个,主逻辑感觉和我的这个差不多,但是我的会TLE最后一个测试点。
下面是我的代码
```
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+10,M=2*1e4+10;
int n,m,s,t;
int h[N],e[M],w[M],ne[M],idx;
int d[N],st[N];
int u,v,ww;
void add(int u,int v,int ww)
{
e[idx]=v;
w[idx]=ww;
ne[idx]=h[u];
h[u]=idx++;
e[idx]=u;
w[idx]=ww;
ne[idx]=h[v];
h[v]=idx++;
}
int spfa(){
memset(d,0x3f,sizeof d);
d[s]=0;
st[s]=1;
queue<int> q;
q.push(s);
while(q.size())
{
auto k=q.front();
q.pop();
st[k]=0;
for(int i=h[k];i!=-1;i=ne[i])
{
int j=e[i];
int tem=max(d[k],w[i]);
if(d[j]>tem)
{
d[j]=tem;
if(!st[j])
{
q.push(j);
st[j]=1;
}
}
}
}
return d[t];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&ww);
add(u,v,ww);
}
cout<<spfa();
return 0;
}
```
by _LJQ_ @ 2023-05-03 14:33:37
@[_LJQ_](/user/635264) 应该是被卡了,试试看随机边目录。
by Dr_Glitch @ 2023-05-03 14:34:09
@[_LJQ_](/user/635264) 不过一般还是推荐用 Dijkstra
by Dr_Glitch @ 2023-05-03 14:36:44
@[Dr_Glitch](/user/123823)
dalao看下呢,这个是题解里面的一个同学写的spfa,这个是可以过的
```
#include<bits/stdc++.h>//懒懒的万能头
#define Maxn 100005
using namespace std;
int ax,axx,n,m,beg,fin,len;
vector<int>plat[Maxn],Len[Maxn];//在这里我使用了vector,只要还是因为懒....
int flag[Maxn],dis[Maxn];//储存是否入队列以及最短路
void add(int a,int b,int c) {//加边(一定要注意是双向的!)
plat[a].push_back(b);
Len[a].push_back(c);
plat[b].push_back(a);
Len[b].push_back(c);
}
queue<int>Q;//(又是懒懒的系统队列)(貌似会比手写得慢一点吧)
void spfa() {
for(int i=1; i<=n; i++)dis[i]=1e9+7,flag[i]=0;//初始化距离无穷大
flag[ax]=1;//起点入队
dis[ax]=0;//起点到起点距离相等
Q.push(ax);//入系统队列(与上面不同)
while(!Q.empty()) {
int t=Q.front();//取队首元素
Q.pop();//弹出队首元素
flag[t]=0;//队首元素出队(flag的队!)(不要看混了)
for(int i=0; i<plat[t].size(); i++) {
int tmp=max(dis[t],Len[t][i]);//唯一和模板不一样的地方
if(dis[plat[t][i]]>tmp) {
dis[plat[t][i]]=tmp;
if(!flag[plat[t][i]]) {
Q.push(plat[t][i]);
flag[plat[t][i]]=1;
}
}
}
}
if(dis[axx]==1e9+7)dis[axx]=-1;//一定要注意题中的-1,不然就wa了
printf("%d\n",dis[axx]);
return ;
}
int main() {
scanf("%d%d%d%d",&n,&m,&ax,&axx);//读入
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&beg,&fin,&len);
add(beg,fin,len);
}
spfa();
}
```
by _LJQ_ @ 2023-05-03 20:49:15
@[_LJQ_](/user/635264) 可能是用了 `vector` 的原因吧,STL 有的时候会快一些
by Dr_Glitch @ 2023-05-05 16:09:59