(로곡1144) 최단거리 계수 #spfa#
15267 단어 최단 경로
제목.
최단로의 개수를 구하다
분석하다.
spfa로 답을 구하고, 디스가 느슨한 상태에서 동시에 답을 구한다.
코드 #include
using namespace std;
struct q{
int x,y,w,next;
}a[2000001]; int go=0;
int n,m,l,d[1000001],ans[1000001],t,list[1000001],ls[1000001];
bool v[1000001];
void spfa(int st){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=2147483647;
list[1]=st; v[st]=ans[st]=1; d[st]=0;
do{
head++;
if (head>n) head=1;
t=ls[list[head]];
while (t>0){
if (d[a[t].x]+1<d[a[t].y]){
d[a[t].y]=d[a[t].x]+1;
ans[a[t].y]=ans[a[t].x];//
if (!v[a[t].y]){
v[a[t].y]=1;
tail++;
if (tail>n) tail=1;
list[tail]=a[t].y;
}
}// , =
else if (d[a[t].x]+1==d[a[t].y])
ans[a[t].y]=(ans[a[t].y]+ans[a[t].x])%100003;// ,
t=a[t].next;
}
v[list[head]]=0;
}while (head!=tail);// bug
for (int i=1;i<=n;i++) printf("%d
",ans[i]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[++go].x=u; a[go].y=v; a[go].next=ls[u]; ls[u]=go;
a[++go].x=v; a[go].y=u; a[go].next=ls[v]; ls[v]=go;
}
spfa(1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)
알고리즘 유형 : 다익스트라 or BFS
다익스트라 풀이
BFS 풀이
SOLVE 1) 풀이 요약 (다익스트라 풀이)
이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다.
가중치가 모두 0 또는 양수이고, 특정...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
spfa로 답을 구하고, 디스가 느슨한 상태에서 동시에 답을 구한다.
코드 #include
using namespace std;
struct q{
int x,y,w,next;
}a[2000001]; int go=0;
int n,m,l,d[1000001],ans[1000001],t,list[1000001],ls[1000001];
bool v[1000001];
void spfa(int st){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=2147483647;
list[1]=st; v[st]=ans[st]=1; d[st]=0;
do{
head++;
if (head>n) head=1;
t=ls[list[head]];
while (t>0){
if (d[a[t].x]+1<d[a[t].y]){
d[a[t].y]=d[a[t].x]+1;
ans[a[t].y]=ans[a[t].x];//
if (!v[a[t].y]){
v[a[t].y]=1;
tail++;
if (tail>n) tail=1;
list[tail]=a[t].y;
}
}// , =
else if (d[a[t].x]+1==d[a[t].y])
ans[a[t].y]=(ans[a[t].y]+ans[a[t].x])%100003;// ,
t=a[t].next;
}
v[list[head]]=0;
}while (head!=tail);// bug
for (int i=1;i<=n;i++) printf("%d
",ans[i]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[++go].x=u; a[go].y=v; a[go].next=ls[u]; ls[u]=go;
a[++go].x=v; a[go].y=u; a[go].next=ls[v]; ls[v]=go;
}
spfa(1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)
알고리즘 유형 : 다익스트라 or BFS
다익스트라 풀이
BFS 풀이
SOLVE 1) 풀이 요약 (다익스트라 풀이)
이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다.
가중치가 모두 0 또는 양수이고, 특정...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
struct q{
int x,y,w,next;
}a[2000001]; int go=0;
int n,m,l,d[1000001],ans[1000001],t,list[1000001],ls[1000001];
bool v[1000001];
void spfa(int st){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=2147483647;
list[1]=st; v[st]=ans[st]=1; d[st]=0;
do{
head++;
if (head>n) head=1;
t=ls[list[head]];
while (t>0){
if (d[a[t].x]+1<d[a[t].y]){
d[a[t].y]=d[a[t].x]+1;
ans[a[t].y]=ans[a[t].x];//
if (!v[a[t].y]){
v[a[t].y]=1;
tail++;
if (tail>n) tail=1;
list[tail]=a[t].y;
}
}// , =
else if (d[a[t].x]+1==d[a[t].y])
ans[a[t].y]=(ans[a[t].y]+ans[a[t].x])%100003;// ,
t=a[t].next;
}
v[list[head]]=0;
}while (head!=tail);// bug
for (int i=1;i<=n;i++) printf("%d
",ans[i]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[++go].x=u; a[go].y=v; a[go].next=ls[u]; ls[u]=go;
a[++go].x=v; a[go].y=u; a[go].next=ls[v]; ls[v]=go;
}
spfa(1);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.