1 条题解

  • 0
    @ 2025-4-9 20:37:29

    解题思路:

    1. 数据建模:把家、学校和各个地铁站当作图的节点,节点间的边权代表从一个节点到另一个节点所需的时间。
    2. 边权计算:步行速度为10千米 / 小时,地铁速度为40千米 / 小时。同一条地铁线路上相邻站点的时间按地铁速度算,其他情况按步行速度算。
    3. 最短路径求解:运用迪杰斯特拉算法找出从家到学校的最短时间路径。

    代码

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
     
    using namespace std;
    const int N = 300;
    const int INF = 9999999;
     
    double map[N][N];
    double num[N];
    int v[N];
    int n,m;
    struct node
    {
        int x,y;
    }q[10001];
    void dijkstra()
    {
        for(int i=0;i<n;i++)
        {
            num[i] = map[0][i];
            v[i] = 0;
        }
        num[0] = 0;
        for(int i=0;i<n;i++)
        {
            int min = INF,k;
            for(int j=0;j<n;j++)
            {
                if(v[j] == 0 && num[j]<min)
                {
                    min = num[j];
                    k = j;
                }
            }
            if(min == INF)
            {
                break;
            }
            v[k] = 1;
            for(int j=0;j<n;j++)
            {
                if(v[j] == 0 && num[j] > num[k] + map[k][j])
                {
                    num[j] = num[k] + map[j][k];
                }
            }
        }
        printf("%.0lf\n",num[1]);
    }
     
    int main()
    {
        while(cin >> q[0].x >> q[0].y >> q[1].x >> q[1].y)
        {
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<=N;j++)
                {
                    map[i][j] = INF;
                }
                map[i][i] = 0;
            }
            n = m = 2;
            while(cin >> q[n].x >> q[n].y)
            {
                if(q[n].x == -1 && q[n].y == -1)
                {
                    m = n;
                    continue;
                }
                if(n!=m)
                {
                    double d = sqrt((double)(q[n].y-q[n-1].y)*(q[n].y - q[n-1].y) + (q[n].x - q[n-1].x)*(q[n].x - q[n-1].x));
                    d = 3*d/2000;
                    map[n][n-1] = d;
                    map[n-1][n] = d;
                }
                n++;
            }
            for(int i=0;i<=n;i++)
            {
                for(int j=0;j<=n;j++)
                {
                    if(map[i][j] == INF)
                    {
                        double d = sqrt((double)(q[j].y-q[i].y)*(q[j].y - q[i].y) + (q[j].x - q[i].x)*(q[j].x - q[i].x));
                        d = 3*d/500;
                        map[i][j] = d;
                        map[j][i] = d;
                    }
                }
            }
            dijkstra();
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    1503
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者