ACGO本题目第一条题解

正常用prim算法是可以过四个点的，有一个会TLE。
为了避免超时TLE，我们进行以下操作：
1、把正常的cin改为快读：
inline void read(int&x)
2、关闭同步流：
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
这样超时的问题就完美解决了。
当然，像我一样无脑#define int long long的也是被这道题给制裁了，因为那样子会MLE爆空间，一定要改回int！
最后，注意这道题要对$10^9+7$进行取模。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2025,MOD=1e9+7;
#define MAXN 0x7f7f7f7f
struct Node{
    int v,w;
};
vector<Node>graph[N];
int n,m,u,v,w,ans;
int dist[N];
bool vis[N];
inline void read(int&x){ //参考第22届NOIP初赛
    bool nega=0;
    int res=0;
    char c=cin.get(); //也可以是getchar();
    while((c>'9'||c<'0')&&c!='-')c=cin.get();
    if(c=='-')nega=1; //根据AC助手的提示，可能有负数且不影响
    else res=c-'0';
    c=cin.get();
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=cin.get();
    }
    if(nega)res*=-1;
    x=res;
}
signed main(){
    ios::sync_with_stdio(0);//关闭同步流
    cin.tie(0);
    cout.tie(0);
    read(n);read(m);
    while(m--){
        read(u);read(v);read(w);
        graph[u].push_back({v,(w+MOD)%MOD});
        graph[v].push_back({u,(w+MOD)%MOD});
    }
    //Prim算法正式开始
    int u=1;
    for(int i=0;i<=n;i++)dist[i]=MAXN;
    dist[u]=0;
    for(int i=1;i<=n;i++){
        u=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<dist[u])
                u=j;
        vis[u]=1;
        for(auto node:graph[u]){
            int v=node.v,w=node.w;
            if(!vis[v])
                dist[v]=min(dist[v],w);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            puts("impossible");
            return 0;
        }
        ans+=dist[i];
    }
    cout<<ans;
    return 0;
}