#include<bits/stdc++.h>
using namespace std;

const int N = 505,INF = INT_MAX;
int n,m,g[N][N],d[N];
bool vis[N];

void Dijk(int s){
    fill(d,d+N,INF);
    d[1] = 0;
    for(int i=0; i<n; i++){
        int u = -1,MIN = INF;
        for(int j=1; j<=n; j++){
            if(!vis[j]&&d[j]<MIN){
                u = j;  MIN = d[j];
            }
        }
        if(u==-1)   return ;
        vis[u] = true;
        for(int v=1; v<=n; v++){
            if(!vis[v]&&g[u][v]!=INF&&d[u]+g[u][v]<d[v])
                d[v] = d[u] + g[u][v];
        }
    }
}
int main()
{
    cin>>n>>m;
    fill(g[0],g[0]+N*N,INF);
    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v] = min(g[u][v],w);
    }
    Dijk(1);
    if(d[n]==INF)   cout<<-1;
    else    cout<<d[n];

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 205,INF = INT_MAX;
int n,m,k,d[N][N];

void floyd(){
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(d[i][k]!=INF&&d[k][j]!=INF&&d[i][k]+d[k][j]<d[i][j])
                    d[i][j] = d[i][k]+d[k][j];
            }
        }
    }
}
int main()
{
    fill(d[0],d[0]+N*N,INF);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++) d[i][i] = 0;
    for(int i=0; i<m; i++){
        int u,v,w;  cin>>u>>v>>w;
        d[u][v] = min(w,d[u][v]);
    }
    floyd();
    while(k--){
        int x,y;    cin>>x>>y;
        if(d[x][y]!=INF)    cout<<d[x][y]<<endl;
        else    cout<<"impossible"<<endl;
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 505,INF = INT_MAX;
int n,m,g[N][N],d[N];//d[i]存放节点i到集合S的最短距离
bool vis[N] = {false};

int prim(){//该题属于稠密图(边多点少)
    fill(d,d+N,INF);
    d[1] = 0;//默认1号点为初始点(点序号从1开始！！！)
    int ans = 0;//最小生成树的边权和
    for(int i=0; i<n; i++){//枚举每一个点，加入集合S(最小生成树)
        int u = -1,MIN = INF;
        for(int j=1; j<=n; j++){
            if(!vis[j]&&d[j]<MIN){
                u = j;  MIN = d[j];
            }
        }
        if(u==-1)   return INF;//找不到一个未访问点与集合S可达，无法产生最小生成树
        vis[u] = true;
        ans += d[u];
        for(int v=1; v<=n; v++){//用节点u优化v到集合S的最短距离
            if(!vis[v]&&g[u][v]!=INF&&g[u][v]<d[v])
            d[v] = g[u][v];
        }
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    fill(g[0],g[0]+N*N,INF);
    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v]=g[v][u] = min(g[u][v],w);
    }
    int ans = prim();
    if(ans==INF) cout<<"impossible";
    else    cout<<ans;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n,m,f[N];
struct edge{
    int u,v,cost;
}e[2*N];
bool cmp(edge a,edge b){
    return a.cost<b.cost;
}
int find(int a){
    if(f[a] != a) f[a] = find(f[a]);
    return f[a];
}
// int find(int x){
//     int c = x;
//     while(x!=f[x]){
//         x = f[x];
//     }
//     while(c!=f[c]){
//         int t = c;
//         c = f[c];
//         f[t] = x;
//     }
//     return x;
// }

int krus(){
    int ans = 0,num = 0;
    for(int i=1; i<=n; i++)  f[i] = i;//注意点的序号从1开始
    sort(e,e+m,cmp);
    for(int i=0; i<m; i++){
        int fu = find(e[i].u),fv = find(e[i].v);
        if(fu!=fv){
            f[fu] = fv;
            ans += e[i].cost;
            num++;
            if(num==n-1)    break;
        }
    }
    if(num!=n-1)    return -1;
    else    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>e[i].u>>e[i].v>>e[i].cost;
    }
    int ans = krus();
    if(ans==-1) cout<<"impossible";
    else    cout<<ans;

    return 0;
}

题目链接 (https://www.acwing.com/problem/content/861/)

算法基础课的859题，为什么最后的测试样例过不了，大佬们看看是哪里的问题

错误的代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n,m,f[N];
struct edge{
    int u,v,cost;
}e[2*N];
bool cmp(edge a,edge b){
    return a.cost<b.cost;
}
// int find(int a){
//     if(f[a] != a) f[a] = find(f[a]);
//     return f[a];
// }
int find(int x){
    int c = x;
    while(x!=f[x]){
        x = f[x];
    }
    while(c!=f[c]){
        int t = c;
        c = f[c];
        f[t] = x;
    }
    return x;
}

int krus(){
    int ans = 0,num = 0;
    for(int i=0; i<n; i++)  f[i] = i;
    sort(e,e+m,cmp);
    for(int i=0; i<m; i++){
        int fu = find(e[i].u),fv = find(e[i].v);
        if(fu!=fv){
            f[fu] = fv;
            ans += e[i].cost;
            num++;
            if(num==n-1)    break;
        }
    }
    if(num!=n-1)    return -1;
    else    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>e[i].u>>e[i].v>>e[i].cost;
    }
    int ans = krus();
    if(ans==-1) cout<<"impossible";
    else    cout<<ans;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int a[50] = {0,1,1};
int f(int n){
    if(n<=2)    return 1;
    if(a[n]!=0)   return a[n];
    else{
        a[n] = f(n-1)+f(n-2);
        return a[n];
    }
}

int main()
{
    int n;  cin>>n;

    f(n);

    for(int i=0; i<n; i++){
        if(i==0)    cout<<a[i];
        else    cout<<" "<<a[i];
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;  cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
        a[i] = i+1;

    do{
        int cnt=0;
        for(int i : a){
            if(cnt==0)  cout<<i;
            else    cout<<" "<<i;
            cnt++;
        }
        cout<<endl;
    }while(next_permutation(a,a+n));

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n,st[10],path[10];

void dfs(int u){
    if(u==n){
        int cnt=0;
        for(int i=0; i<n; i++){
            if(cnt==0)  cout<<path[i];
            else    cout<<" "<<path[i];
            cnt++;
        }
        cout<<endl;
        return ;
    }
    for(int i=1; i<=n; i++){
        if(!st[i]){
            st[i] = 1;
            path[u] = i;
            dfs(u+1);
            st[i] = 0;
        }
    }
}

int main()
{
    cin>>n;

    dfs(0);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,st[18];//0表未考虑，1表选，2表不选

void dfs(int x){
    if(x>n){
        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(st[i]==1){
                if(cnt==0)    printf("%d",i);
                else    printf(" %d",i);
                cnt++;
            }
        }
        cout<<endl;
        return ;
    }

    st[x] = 1;
    dfs(x+1);
    st[x] = 0;

    st[x] = 2;
    dfs(x+1);
    st[x] = 0;
}

int main()
{
    cin>>n;

    dfs(1);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int p[N],cnt;//数组p存素数，所存元素等于其下标，cnt为素数个数
bool st[N];//表示下标对应的数是否已被筛掉

void get_prime(){
    for(int i=2; i<N; i++){//从小到大枚举可能的素数
        if(!st[i]){//如果未被筛掉说明是素数
            st[i] = true;
            p[i] = i;//将素数存入数组
            cnt++;
            for(int j=i+i; j<N; j+=i)    st[j] = true;  //将该素数的倍数都筛掉
        }
    }
}

int main()
{
    get_prime();//先打印素数表
    int n;
    while(cin>>n && n){

        for(int i=2; i<cnt; i++){//从最小到大枚举素数
            if(p[i]!=0 && p[n-p[i]]!=0){//如果所存元素非0说明是素数，并判断是否存在与自身相加和为n的素数
                printf("%d = %d + %d\n",n,p[i],p[n-p[i]]);
                //因为是从小到大枚举，第一个查找到的一定最小，其对应的素数与自身之差最大
                break;
            }
        }
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int p[N],cnt;//数组p存素数，所存元素等于其下标，cnt为素数个数
bool st[N];//表示下标对应的数是否已被筛掉

void get_prime(){
    for(int i=2; i<N; i++){//从小到大枚举可能的素数
        if(!st[i]){//如果未被筛掉说明是素数
            st[i] = true;
            p[i] = i;//将素数存入数组
            cnt++;
            for(int j=i+i; j<N; j+=i)    st[j] = true;  //将该素数的倍数都筛掉
        }
    }
}

int main()
{
    get_prime();//先打印素数表
    int n;
    while(cin>>n && n){

        for(int i=2; i<cnt; i++){//从最小到大枚举素数
            if(p[i]!=0 && p[n-p[i]]!=0){//如果所存元素非0说明是素数，并判断是否存在与自身相加和为n的素数
                printf("%d = %d + %d\n",n,p[i],p[n-p[i]]);
                //因为是从小到大枚举，第一个查找到的一定最小，其对应的素数与自身之差最大
                break;
            }
        }
    }

    return 0;
}