社区讨论
提交了20遍了,所有spfa都是CE,求大神
P1339[USACO09OCT] Heat Wave G参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi5h8kmn
- 此快照首次捕获于
- 2025/11/19 12:02 4 个月前
- 此快照最后确认于
- 2025/11/19 12:02 4 个月前
CPP
#include<iostream>
#include<cstring>
using namespace std;
int u[10001],v[10001],w[10001],first[10001],next[10001];
int dis[10001],book[10001];
int que[10001],head=1,tail=2;
int n,m;
int s,e,k;
int spfa()
{
que[head]=s;
book[s]=1;
while(head<tail)
{
k=first[que[head]];
while(k!=-1)
{
if(dis[v[k]]>dis[u[k]]+w[k])
{
dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0)
{
que[tail]=v[k];
tail++;
book[v[k]]=1;
}
}
k=next[k];
}
book[que[head]]=0;
head++;
}
}
int main()
{
cin>>n>>m>>s>>e;
memset(dis,0x7f,sizeof(dis));
memset(first,-1,sizeof(first));
dis[s]=0;
for(int i=1;i<=2*m;i=i+2)
{
cin>>u[i]>>v[i]>>w[i];
next[i]=first[u[i]];
first[u[i]]=i;
next[i+1]=first[v[i]];
first[v[i]]=i+1;
}
spfa();
cout<<dis[e]<<endl;
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...