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; }

 

좋은 웹페이지 즐겨찾기