【模拟题】心灵的抚慰

客官°小女子只卖身不卖艺 2022-06-09 03:48 122阅读 0赞

### 心灵的抚慰 ###

【问题描述】  
病毒问题解决后，神牛们的心灵久久不能平静。他可以从一个程序联想到一些相似的程序。比如从程序1联想到2，从2联想到4，从4联想到6，从6联想到9……就像搜索一样一步一步越陷越深。不过同一种联想他只会联想一次。比如1、2之间他进行了一次联想，那么他不会再重新联想1到2，或2到1。如果他刚开始时想到的程序能够经过联想若干次后联想回到原程序，那不就乱回来了吗？由于神牛马上就要开乱，请在1秒内告诉他，他需要想哪个程序，以便乱回来。  
给出一些程序和他们互相联想的关系（如果两个程序A、B有联系，神牛可以从A联想到B，也可以从B联想到A，但A、B之间神牛最多联想一次），请告诉神牛他需要想哪个程序，以便在最短的时间内乱回来，并输出这个最短时间。  
【输入格式】heart.in  
第一行有两个正整数N，M，分别表示程序个数和有多少对程序可以被神牛直接互相联想。  
以下M行，每行三个正整数，分别表示一种联想的两端的程序的编号（从1开始），以及进行这种联想所需要的最短时间(≤3500)。  
【输出格式】heart.out  
如果神牛无论如何都再也乱不回来了，输出“He will never come back.”。  
如果神牛能够乱回来，请输出神牛会乱多长时间。  
【输入样例】  
4 3  
1 2 10  
1 3 20  
1 4 30  
【输出样例】  
He will never come back.  
【数据规模】  
对于100% 的数据，n≤250。

这是一个无向图的最小环问题，可以用Floyd算法来解决。  
核心代码如下：

for (int k=1;k<=n;k++)
        {
            for (int i=1;i<=k-1;i++)
                for (int j=i+1;j<=k-1;j++)
                    ans=min(ans,dis[i][j]+map[j][k]+map[k][i]);
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    long long map[300][300],dis[300][300],n,ans=1e15,m;
    
    int main()
    {
        freopen("heart.in","r",stdin);
        freopen("heart.out","w",stdout);
        memset(map,127/3,sizeof(map));
        memset(dis,127/3,sizeof(dis));
        int x,y,z;
        cin>>n>>m;
        for (int i=1;i<=m;i++)
        {
            cin>>x>>y>>z;
            map[x][y]=map[y][x]=z;
            dis[x][y]=dis[y][x]=z;
        }
        for (int k=1;k<=n;k++)
        {
            for (int i=1;i<=k-1;i++)
                for (int j=i+1;j<=k-1;j++)
                    ans=min(ans,dis[i][j]+map[j][k]+map[k][i]);
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
        if (ans>=1e15)
        cout<<"He will never come back.";
        else cout<<ans;
        return 0;
    }