题目链接

代码献上

#include<bits/stdc++.h>
using namespace std;
int n,m,g[1001][1001],minn[1001];
bool u[1001];
int main()
{
	while(cin>>n)
	{
		if(!n) return 0;
		cin>>m;
		memset(g,0,sizeof(g));
		for(int i=0;i<m;i++) 
		{
			int x,y,cnt;
			cin>>x>>y>>cnt;
			g[x][y]=cnt;
		}
		memset(minn,0x7f,sizeof(minn));
		minn[1]=0;
		memset(u,1,sizeof(u));
		for(int i=1;i<=n;i++)
		{
			int k=0;
			for(int j=1;j<=n;j++) if(u[j]&&(minn[j]<minn[k])) k=j;
			u[k]=0;
			for(int j=1;j<=n;j++) if(u[j]&&(g[k][j]<minn[j])) minn[j]=g[k][j];
		}
		int total=0;
		for(int i=1;i<=n;i++) total+=minn[i];
		if(!total) cout<<"No way!";
		else cout<<total;
		cout<<endl;
	}
}