Rqnoj 319 FLOYD

admin

[code=Cpp width=700px]
#include <iostream>
using namespace std;
int e[999][999],n,m,i,j,k,t1,t2,t3,a[999];
int main()
{
        cin >> n;

        for(i=1;i<=n;i++)
        {
                cin >> a >> t2 >> t3;
                e[t2]=e[t3]=1;
                e[t2]=e[t3]=1;
        }

        for(i=1;i<=n;i++)
        {
                for(j=1;j<=n;j++)
                {
                        if(e[j]==0 && i!=j)
                                e[j]=99999;
                }
        }
        for(k=1;k<=n;k++)
        {
                for(i=1;i<=n;i++)
                {
                        for(j=1;j<=n;j++)
                        {
                                if(e[k]!=99999 && e[k][j]!=99999 && e[j]>e[k]+e[k][j])
                                        e[j]=e[k]+e[k][j];
                        }
                }
        }
        int t,min=999999;
        for(i=1;i<=n;i++)
        {
                t=0;
                for(j=1;j<=n;j++)
                        t=t+a[j]*e[j];
                if(t<min)
                        min=t;
        }
        cout << min;
        return 0;
}
[/code]