HDOJ_1142 최단거리 디제스트라+실검
6666 단어 최단로
이 문제는 사람을 매우 붕괴시킨다. 처음에 계속 runtime error로 인해 나는 안개가 자욱해졌다. 한참 동안 높아졌는데, 내 맵이 초기화된 문장은 조건 표현식을 해야 하는데 풀지 못했다.
오늘 갑자기 또runtime error를 만들어서 나에게 물어봤다. 나는 어제 자신의 컴퓨터에서 제출했는데 나중에 그는 제출할 수 없었다. 나는 어리둥절했다. 나중에야 c++로 제출해야 한다는 것을 발견했는데 여전히 이해가 되지 않았다
#include<stdio.h>
#include<string.h>
#define MAX 1000010
//#define MAX_1 1001
int map[1001][1001],dis[1001];
int res[1001];
int n,m;
bool visit[1001];
void dijkstra(int k)
{
int u,i,j,min,x;
for(i=1;i<=n;++i)
{
visit[i]=false;
dis[i]=map[2][i];
}
visit[2]=true;
if(min==MAX)
return ;
for(i=2;i<=n;++i)
{
min=MAX;
for(j=1;j<=n;++j)
{
if(!visit[j]&&min>dis[j])
{
u=j;
min=dis[j];
}
}
visit[u]=true;
for(x=1;x<=n;++x)
{
if(!visit[x]&&dis[x]>dis[u]+map[x][u])
{
dis[x]=dis[u]+map[x][u];
}
}
}
}
int find(int v)
{
int i;
if(res[v]!=-1)
return res[v];
if(v==2)
return 1;
res[v]=0;
for(i=1;i<=n;++i)
{
if(map[i][v]!=MAX && dis[i]<dis[v])
res[v]+=find(i);
}
return res[v];
}
int main()
{
int i,j,a,b,value;
while(scanf("%d",&n)!=EOF&&n)
{
scanf("%d",&m);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
map[i][j]=MAX;
map[i][j] = i == j ? 0 : MAX;
}
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&value);
map[a][b]=map[b][a]=value;
}
dijkstra(2);
memset(res,-1,sizeof(res));
printf("%d
",find(1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Uva10986-Sending email텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.