当前位置:网站首页>L - Jungle roads (minimum spanning tree)
L - Jungle roads (minimum spanning tree)
2022-06-30 15:00:00 【Rabbit doesn't like radish】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200,MAX=0x3f3f3f3f;
int n;
int from,to,w;
int dist[N],map[N][N];
bool biao[N];
int prim()// Algorithm part template
{
memset(dist,0x3f,sizeof(dist));
memset(biao,0,sizeof(biao));
int t=1,sum=0;
dist[1]=0,biao[1]=1;
for(int i=0;i<n-1;i++)
{
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],map[t][j]);
t=-1;
for(int j=1;j<=n;j++)
{
if(!biao[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
sum+=dist[t];
biao[t]=1;
}
return sum;
}
int main()
{
while(cin>>n&&n)
{
int t=n-1;
memset(map,0x3f,sizeof(map));
while(t--)
{
char c;
cin>>c;
int kk=c-'A'+1;// Convert characters into numbers as soon as you enter them ,
int m;
cin>>m;
while(m--)
{
char cc;
int mm;
cin>>cc;
int ll=cc-'A'+1;
cin>>mm;
map[kk][ll]=map[ll][kk]=mm;// The path should be bidirectional
}
}
int sum=prim();
cout<<sum<<endl;
}
return 0;
}
The question :
It is still to find the minimum path length ,
But the peculiar thing about this topic is , The place is indicated by letters , But that's okay , Then turn it into numbers again , How wise
边栏推荐
- 浅析卧式加工中心上不规则台阶孔存在问题
- Binary rotation array (2)
- Using member variables and member functions of a class
- LIS error: this configuration section cannot be used in this path
- jsPlumb. Deleteeveryconnection is not a function & jsplumb clear canvas jsplumb delete all nodes and all connections
- Sum of squares of two pointers
- 1 figure to explain the difference and connection between nodejs and JS
- Solve the problem that codeblocks20.03 on win11 cannot run for the first time
- V3 02——What‘s new in Chrome extensions
- Sum of CCF digits (full mark code + problem solving idea) 201512-1
猜你喜欢

Component communication mode

Matlab judge palindrome number (only numbers)

Not satisfied with markdown native code block style? Try this beautify code screenshot tool~~

val_ Loss decreases first and then increases or does not decrease but only increases

CCF window (Full Score code + problem solving idea) March 2, 2014

Matlab function for limit, definite integral, first-order derivative, second-order derivative (classic examples)

CCF elimination games (Full Score code + problem solving ideas + skill summary) February 2, 2015

Lihongyi machine learning 2020 homework summary

1 figure to explain the difference and connection between nodejs and JS

CCF sequence segmentation (Full Score code + problem solving idea) 201509 -1
随机推荐
The kth largest element in the sorted array
1135: paired base chain
Quick sort (C language)
Lost connection to the flow server (0 retries remaining): |Out of retries, exiting! Error reporting solution (flow)
Implement a long-click list pop-up box on apiccloud
Steps for commissioning of vertical machining center
PS tip: the video frame to Layer command cannot be completed because dynamiclink is not available
LIS error: this configuration section cannot be used in this path
1137: encrypted medical record
Sum of squares of two pointers
Machine learning feature selection
JS time conversion standard format, timestamp conversion standard format
Repair of incorrect deletion of win10 boot entry
1019 general palindromic number (20 points)
Matlab to find prime pairs within 100
JS to realize simple lottery function
1027 colors in Mars (20 points)
[extensive reading of papers] a delicious recipe analysis framework for exploring multi modal recipes with variable attributes
CCF sequence segmentation (Full Score code + problem solving idea) 201509 -1
Judgment of deep learning experiment results