社区讨论
求救求救 spfa 过不了
P3371【模板】单源最短路径(弱化版)参与者 10已保存回复 13
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 13 条
- 当前快照
- 1 份
- 快照标识符
- @mi7cuppv
- 此快照首次捕获于
- 2025/11/20 19:35 4 个月前
- 此快照最后确认于
- 2025/11/20 22:03 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int number,way,mapp[3002][3002],x,y,distance1,start,dis[30000002];
int head,tail,q[300002],vis[300002],v;
void SPFA(int s){
for(int i=1;i<=number;i++)dis[i]=9999999;
head=0;tail=1;
dis[s]=0;vis[s]=1;q[tail]=s;
while(head<tail){
head++;v=q[head];vis[v]=0;
for(int i=1;i<=number;i++){
if(mapp[v][i]>0&&dis[i]>dis[v]+mapp[v][i]){
dis[i]=dis[v]+mapp[v][i];
if(!vis[i]){
tail++;q[tail]=i;vis[i]=1;
}
}
}
}
}
int main(){
cin>>number>>way>>start;
for(int i=1;i<=way;i++){
cin>>x>>y>>distance1;
if(mapp[x][y]!=0)mapp[x][y]=min(mapp[x][y],distance1);
else mapp[x][y]=distance1;
}
SPFA(start);
for(int i=1;i<=number;i++)cout<<dis[i]<<" ";
return 0;
}
回复
共 13 条回复,欢迎继续交流。
正在加载回复...