最短路径问题

ゞ浴缸里的玫瑰 2022-07-10 16:29 187阅读 0赞

[sdut原题链接][sdut]

最短路径问题  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
平面上有n个点（n<=100），每个点的坐标均在-10000～10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短距离。

Input  
第1行为整数n。  
第2行到第n+1行（共n行），每行两个整数x和y，描述了一个点的坐标（以一个空格分隔）。  
第n+2行为一个整数m，表示图中连线的个数。  
此后的m行，每行描述一条连线，由两个整数i和j组成，表示第1个点和第j个点之间有连线。  
最后一行：两个整数s和t，分别表示源点和目标点。

Output  
仅1行，一个实数（保留两位小数），表示从s到t的最短路径长度。

Example Input  
5  
0 0  
2 0  
2 2  
0 2  
3 1  
5  
1 2  
1 3  
1 4  
2 5  
3 5  
1 5

Example Output  
3.41

Hint

Author

以下为accepted代码——Floyd

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #define INF 0x3f3f3f3f
    int x[104], y[104];
    double D[104][104];
    int main()
    {
        int n, m, i, j, k, u, v, s, t;
        scanf("%d", &n);
        for(i = 0; i <= n; i++)
        {
            for(j = 0; j <= n; j++)
            {
                if(i == j)
                    D[i][j] = 0;
                else
                    D[i][j] = INF;
            }
        }
        for(i = 1; i <= n; i++)
        {
            scanf("%d %d", &x[i], &y[i]);
        }
        scanf("%d", &m);
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d", &u, &v);
            if(D[u][v] > sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2)))
                D[u][v] = D[v][u] = sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2));
        }
        for(k = 1; k <= n; k++)
        {
            for(i = 1; i <= n; i++)
            {
                for(j = 1; j <= n; j++)
                {
                    if(D[i][j] > D[i][k] + D[k][j])
                        D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
        scanf("%d %d", &s, &t);
        printf("%.2lf\n", D[s][t]);
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 4ms
    Take Memory: 200KB
    Submit time: 2017-02-17 21:11:24
    ****************************************************/

以下为accepted代码——Dijkstra

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #define INF 0x3f3f3f3f
    double map[104][104], dist[104];
    int n, m;
    int x[104], y[104], vis[104];
    void Dijkstra(int v)
    {
        int i, j, k;
        for(i = 1; i <= n; i++)//dist数组的初始化
        {
            dist[i] = map[v][i];
            vis[i] = 0;
        }
        dist[v] = 0;
        vis[v] = 1;
    
        for(i = 0; i < n-1; i++)
        {
            int min = INF, u = v;
            for(j = 1; j <= n; j++)//寻找未标记结点的最小值
            {
                if(vis[j] == 0 && dist[j] < min)
                {
                    u = j;
                    min = dist[j];
                }
            }
            vis[u] = 1;
    
            for(k = 1; k <= n; k++)//更新最短路
            {
                if(vis[k] == 0 && map[u][k] < INF && dist[k] > dist[u] + map[u][k])
                {
                    dist[k] = dist[u] + map[u][k];
                }
            }
        }
    }
    int main()
    {
        int i, j, u, v, s, t;
        scanf("%d", &n);
        memset(vis, 0, sizeof(vis));
        for(i = 0; i <= n; i++)
        {
            for(j = 0; j <= n; j++)
            {
                if(i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = INF;
            }
        }
        for(i = 1; i <= n; i++)
        {
            scanf("%d %d", &x[i], &y[i]);
        }
        scanf("%d", &m);
        for(i = 0; i < m; i++)
        {
            scanf("%d %d", &u, &v);
            if(map[u][v] > sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2)))
                map[u][v] = map[v][u] = sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2));
        }
        scanf("%d %d", &s, &t);
        Dijkstra(s);
        printf("%.2lf\n", dist[t]);
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-02-17 21:47:31
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2013/pid/1867