floyd求调
查看原帖
floyd求调
1028442
linruizhe111楼主2024/8/12 13:10
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
long long n,m,f[510][510],k,a[510];
int main()
{
    cin>>n>>k>>m;
    for(long long i=1;i<=k;i++)cin>>a[i];
    memset(f,0x3f,sizeof(f));
    for(long long i=1;i<=m;i++){
        long long x,y,z;
        cin>>x>>y>>z;
        f[x][y]=f[y][x]=z;  
    }   
    for(long long i=1;i<=n;i++)
        f[i][i]=0;
    for(long long l=1;l<=n;l++) 
        for(long long i=1;i<=n;i++)
            for(long long j=1;j<=n;j++)
                if(i!=j&&j!=l&&i!=l)
                    f[i][j]=min(f[i][j],f[i][l]+f[l][j]);
//    for(long long i=1;i<=n;i++)    {
//        for(long long j=1;j<=n;j++)
//            cout << f[i][j]<<" ";
//        cout << endl;
//    }
    long long ans=0x3f,res;
    for(long long i=1;i<=n;i++){
        long long cnt=0;
        for(long long j=1;j<=k;j++)  
            cnt+=f[i][a[j]];
        if(cnt<ans)ans=cnt,res=i;
    }
    cout << res;
 	return 0;//orz
}

2024/8/12 13:10
加载中...