Dijkstra算法+二维结构体数组

缺乏、安全感 2022-07-12 08:46 173阅读 0赞

think:  
1Dijkstra算法  
2二维结构体数组

[sdut原题链接][sdut]

数据结构实验之图论七：驴友计划  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
做为一个资深驴友，小新有一张珍藏的自驾游线路图，图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况，现在请你编写一个程序，找出一条出发地到目的地之间的最短路径，如果有多条路径最短，则输出过路费最少的一条路径。

Input  
连续T组数据输入，每组输入数据的第一行给出四个正整数N,M，s，d，其中N(2 <= N <= 500)是城市数目，城市编号从0～N-1，M是城市间高速公路的条数，s是出发地的城市编号，d是目的地的城市编号；随后M行，每行给出一条高速公路的信息，表示城市1、城市2、高速公路长度、收费额，中间以空格间隔，数字均为整数且不超过500，输入数据均保证有解。

Output  
在同一行中输出路径长度和收费总额，数据间用空格间隔。

Example Input  
1  
4 5 0 3  
0 1 1 20  
1 3 2 30  
0 3 4 10  
0 2 2 20  
2 3 1 20

Example Output

3 40

Hint

Author  
xam

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #define INF 0x3f3f3f3f
    int n, m;
    int vis[504];
    struct node
    {
        int data;
        int ans;
    }map[504][504], dist[104], min;
    void Dijkstra(int v)
    {
        int i, j, k;
        for(i = 0; i < n; i++)
        {
            dist[i] = map[v][i];
            vis[i] = 0;
        }
        vis[v] = 1;
        dist[v].data = 0;
        dist[v].ans = 0;
    
        for(i = 0; i < n-1; i++)
        {
            int u = v;
            min.data = INF;
            min.ans = INF;
            for(j = 0; j < n; j++)
            {
                if(vis[j] == 0 && dist[j].data == min.data && dist[j].ans < min.ans)
                {
                    u = j;
                    min = dist[j];
                }
                if(vis[j] == 0 && dist[j].data < min.data)
                {
                    u = j;
                    min = dist[j];
                }
            }
            vis[u] = 1;
    
            for(k = 0; k < n; k++)
            {
                if(vis[k] == 0 && map[u][k].data < INF)
                {
                    if(dist[k].data > dist[u].data + map[u][k].data)
                    {
                        dist[k].data = dist[u].data + map[u][k].data;
                        dist[k].ans = dist[u].ans + map[u][k].ans;
                    }
                    if(dist[k].data == dist[u].data + map[u][k].data && dist[k].ans > dist[u].ans + map[u][k].ans)
                    {
                        dist[k].data = dist[u].data + map[u][k].data;
                        dist[k].ans = dist[u].ans + map[u][k].ans;
                    }
                }
            }
        }
    }
    int main()
    {
        int T, s, t, i, j, u, v, x, y;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%d %d %d %d", &n, &m, &s, &t);
            for(i = 0; i < n; i++)
            {
                for(j = 0; j < n; j++)
                {
                    if(i == j)
                    {
                        map[i][j].data = 0;
                        map[i][j].ans = 0;
                    }
                    else
                    {
                        map[i][j].data = INF;
                        map[i][j].ans = INF;
                    }
                }
            }
            for(i = 0; i < m; i++)
            {
                scanf("%d %d %d %d", &u, &v, &x, &y);
                map[u][v].data = map[v][u].data = x;
                map[u][v].ans = map[v][u].ans = y;
            }
            Dijkstra(s);
            printf("%d %d\n", dist[t].data, dist[t].ans);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 128KB
    Submit time: 2017-02-19 11:17:47
    ****************************************************/

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