3363数据结构实验之图论七：驴友计划

ゝ一世哀愁。 2022-07-14 04:41 105阅读 0赞

[数据结构实验之图论七：驴友计划  
][Link 1]  
Floyd算法

#include <stdio.h>  
    #include <stdlib.h>  
    #include <string.h>  
    #define INF 0x3f3f3f3f  
    using namespace std;  
    struct node  
    {  
        int l;  
        int w;  
    }a[510][510];  
    
    void floyd(int n)  
    {  
         int k, i, j;  
         for(k=0; k<n; k++)  
            for(i=0; i<n; i++)  
               for(j=0; j<n; j++)  
         {  
             if(a[i][j].l>a[i][k].l+a[k][j].l)  
             {  
                 a[i][j].l=a[i][k].l+a[k][j].l;  
                 a[i][j].w=a[i][k].w+a[k][j].w;  
             }  
             if(a[i][j].l==a[i][k].l+a[k][j].l)  
             {  
                 if(a[i][j].w>a[i][k].w+a[k][j].w)  
                    a[i][j].w=a[i][k].w+a[k][j].w;  
             }  
    
         }  
    
    }  
    
    int main()  
    {  
        int t, n, m, i, j, s, d;  
        scanf("%d", &t);  
        while(t--)  
        {  
            scanf("%d %d %d %d", &n, &m, &s, &d);  
            for(i=0; i<n; i++)  
                for(j=0; j<n; j++)  
                   {  
                       if(i!=j)  
                       {  
                           a[i][j].l = INF;  
                           a[i][j].w = INF;  
                       }  
                       else  
                       {  
                           a[i][j].l = 0;  
                           a[i][j].w = 0;  
                       }  
                   }  
            int v1, v2, length, cost;  
            for(i=0; i<m; i++)  
            {  
                scanf("%d %d %d %d", &v1, &v2, &length, &cost);  
                a[v1][v2].l = length;  
                a[v1][v2].w = cost;  
                a[v2][v1] = a[v1][v2];  
            }  
            floyd(n);  
            printf("%d %d\n", a[s][d].l, a[s][d].w);  
    
        }  
    }

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