首页 > 代码库 > 人活着系列之开会(Floy)

人活着系列之开会(Floy)

2024-07-15 20:09:12   222人阅读

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2930

题意：所有点到Z点的最短距离。因为岛名由大小写字母组成，所以岛最多有52。

#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#define N 1000001using namespace std;int n;int map[60][60];void init(){    for(int i=0; i<=52; i++)    {        for(int j=0; j<=52; j++)        {            map[i][j]=N;            map[j][i]=N;        }        map[i][i]=0;    }}void floy(){    for(int k=0; k<=52; k++)    {        for(int i=0; i<=52; i++)        {            for(int j=0; j<=52; j++)            {                if(map[i][j]>map[i][k]+map[k][j])                {                    map[i][j]=map[i][k]+map[k][j];                }            }        }    }}int main(){    int xx,yy,zz;    char x[100],y[100];    while(scanf("%d",&n)!=EOF)    {        init();        while(n--)        {            scanf("%*c%s%s%d",x,y,&zz);//注意本题的坑            if(x[0]>=‘A‘&&x[0]<=‘Z‘)            {                xx=x[0]-‘A‘;            }            else xx =x[0]-‘a‘+26;            if(y[0]>=‘A‘&&y[0]<=‘Z‘)            {                yy=y[0]-‘A‘;            }            else yy=y[0]-‘a‘+26;            if(map[xx][yy]>zz)            {                map[xx][yy]=zz;                map[yy][xx]=zz;            }        }        floy();        int k=0,min=N;        for(int i=0; i<25; i++)        {            if(map[i][25]<min)            {                min=map[i][25];                k=i;            }        }        printf("%c %d\n",‘A‘+k,min);    }    return 0;}

 


联系
我们