当前位置:网站首页>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
边栏推荐
- Solve the problem that codeblocks20.03 on win11 cannot run for the first time
- The difference between settimeout() and setinterval()
- 高精度CNC加工中心为什么会出现误差?这4个原因你要注意!
- Querywrapper in mybaits plus
- Binary rotation array (1)
- 1151 LCA in a binary tree (30 points)
- The difference between queue and stack
- JS to realize simple lottery function
- day02
- Computer screenshot how to cut the mouse in
猜你喜欢

CCF call auction (full mark code + problem solving ideas + skill summary) 201412 - 3

LIS error: this configuration section cannot be used in this path

Knowledge learned from the water resources institute project

@PathVariable
[email protected][])"/>NoViableAltException([email protected][])

CCF string matching (Full Score code + problem solving ideas + skill summary) March 3, 2014

Detailed explanation of settimeout() and setinterval()
![[buuctf] [actf2020 freshman competition]include](/img/42/50439290177fdea5f431e315cac1a1.jpg)
[buuctf] [actf2020 freshman competition]include

CCF command line options (Full Score code + problem solving ideas + skill summary) March 3, 2014

JS to realize simple lottery function
随机推荐
1135: paired base chain
How to program and process such parts?
Invalid argument during startup: Failed to open the . conf file: redis-window
1137: encrypted medical record
Double pointer circular linked list
Matlab judges the number of same purchases
1134: Legal C identifier query
1130: find the first character that appears only once
Text matching - [naacl 2021] augsbert
How many questions can you answer for the interview of Mechanical Engineer?
Lost connection to the flow server (0 retries remaining): |Out of retries, exiting! Error reporting solution (flow)
1149 dangerous goods packaging (25 points)
机械工程师面试的几个问题,你能答上来几个?
Finding the median of two arrays by dichotomy
CCF drawing (full mark code + problem solving ideas + skill summary) February 2, 2014
Sum of CCF digits (full mark code + problem solving idea) 201512-1
高清机械原理 · 机械设计经典动图
V3 03_ Getting started
For loop and promise to solve the problem of concurrent callback
Distributed -- openresty+lua+redis