社区讨论
为什么SPFA+SLF会被卡?
P2984[USACO10FEB] Chocolate Giving S参与者 5已保存回复 13
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 13 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hnn70
- 此快照首次捕获于
- 2025/11/20 05:02 4 个月前
- 此快照最后确认于
- 2025/11/20 05:09 4 个月前
看题解裸的SPFA都能过
而且我前9个点跑的那么那么快..........
为啥最后一点T
CPP**#include <iostream>**
**#include <cstdio>**
**#include <cstdlib>**
**#include <queue>**
**#include <deque>**
**#define ll long long**
**using namespace std;**
**int n,m,b,v[100001],w[100001],next[100001],st[100001],fr,to,wi,topt,p;**
**ll dis[50001];**
**bool f[50001];**
**void add (int x,int y,int z)**
**{**
**w[++topt]=z;**
**v[topt]=y;**
**next[topt]=st[x];**
**st[x]=topt;**
**}**
**int main()**
**{**
**deque<int>q; q.clear();**
**scanf("%d%d%d",&n,&m,&b);**
**for (int i=1;i<=m;i++)**
**{**
**scanf("%d%d%d",&fr,&to,&wi);**
**add(fr,to,wi);**
**add(to,fr,wi);**
**}**
**for (int i=1;i<=50000;i++) dis[i]=0x7fffffff;**
**dis[1]=0; q.push_back(1); f[1]=1;**
**while (!q.empty())**
**{**
**int x=q.front(); q.pop_front(); f[x]=0;**
**p=st[x];**
**while (p)**
**{**
**if (dis[x]+w[p]<dis[v[p]])**
**{**
**dis[v[p]]=dis[x]+w[p];**
**if (!f[v[p]])**
**{**
**if (dis[v[p]]<dis[x]) q.push_front(v[p]);else q.push_back(v[p]);**
**f[v[p]]=1;**
**}**
**}**
**p=next[p];**
**}**
**}**
**for (int i=1;i<=b;i++)**
**{**
**int xx,yy; scanf("%d%d",&xx,&yy);**
**printf("%d\n",dis[xx]+dis[yy]);**
**}**
**return 0;**
**}**
回复
共 13 条回复,欢迎继续交流。
正在加载回复...