您的位置: 首页  >  IT文章  >  hdu2112 一个人的旅行 最短路问题，dijkstra算法

hdu2112 一个人的旅行 最短路问题，dijkstra算法

分类: IT文章 • 2024-10-15 21:35:00

模板题不多说，字符处理部分有人使用一个函数转化，我直接在主函数里转化的。把地点名转化成对应的点。

能到输出最短路，不能到输出-1，但是容易遗漏的是，有可能起点与终点相同，输出0。。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define INF 200000000
int dis[151],visit[151],map[151][151],t;
void dij(int a,int b)
{
    int i,j,min,v;
    memset(visit,0,sizeof(visit));
    for(i=1;i<=t;i++)
        dis[i]=INF;
    dis[a]=0;
    for(i=1;i<=t;i++)
    {
        for(j=1,min=INF,v=a;j<=t;j++)
        {
            if(visit[j]!=1&&dis[j]<min)
            {
                min=dis[j];
                v=j;
            }
        }
        visit[v]=1;
        for(j=1;j<=t;j++)
        {
            if(dis[v]+map[v][j]<dis[j])
                dis[j]=dis[v]+map[v][j];
        }
    }
    if(dis[b]==INF)
        printf("-1
");
    else
    printf("%d
",dis[b]);
}

int main()
{
    int i,j,k,l,s[101],acc[151][101],a,b,n,time,flag;
    while(scanf("%d",&n)!=EOF&&n!=-1)
    {
        t=1;flag=0;
        scanf("%s",&acc[1]);
        scanf("%s",&s);
        if(strcmp(s,acc[1])!=0)
        {
            strcpy(acc[++t],s);
            flag=1;
        }
        for(i=1;i<=150;i++)
            for(j=1;j<=150;j++)
                map[i][j]=INF;
        for(i=1;i<=n;i++)
        {
            a=0;b=0;
            scanf("%s",&s);
            for(j=1;j<=t;j++)
                if(strcmp(acc[j],s)==0)
                {
                    a=j;
                    break;
                }
            if(a==0)
            {
                strcpy(acc[++t],s);
                a=t;
            }
            scanf("%s",&s);
            for(j=1;j<=t;j++)
                if(strcmp(acc[j],s)==0)
                {
                    b=j;
                    break;
                }
            if(b==0)
            {
                strcpy(acc[++t],s);
                b=t;
            }
            scanf("%d",&time);
            if(map[a][b]>time)
            {
                map[a][b]=time;
                map[b][a]=time;
            }
        }
        if(flag==1)
        dij(1,2);
        else
        {
            printf("0
");
            continue;
        }
    }
    return 0;
}

相关推荐