# Shortest path - unimpeded project

## Smooth works

HDU - 1863
The goal of the provincial government's "unblocking project" is to make highway traffic possible between any two villages in the province (but there is not necessarily a direct highway connection, as long as it can be reached indirectly through the highway). After investigation and evaluation, the cost of several roads that may be constructed is listed in the statistical table. Now, please write a program to calculate the lowest cost for the smooth flow of the whole province.
The Input test Input contains several test cases. The first line of each test case shows the number of evaluated roads N, the number of villages m (< 100); the next N
Rows correspond to the cost of roads between villages. Each row gives a pair of positive integers, which are the number of two villages and the cost of roads between the two villages (also positive integers). For simplicity, villages are numbered from 1 to M. When N is 0, all inputs are ended and the corresponding results are not output.
Output for each test case, output the lowest cost required for smooth operation of the whole province in one line. If the statistics are not enough to ensure smooth flow, output "?".
Sample Input
```3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100```
Sample Output
```3
?```

```#include <iostream>
#include <algorithm>
using namespace std;
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxm = 101;
const int maxn = 5055;
int N,M;
int edgenum = 0;
int f[maxm];
struct node
{
int from,to,w;
node(int a,int b,int c)
{
from = a;
to = b;
w = c;
}
}edge[maxn];
bool cmp(node a, node b)
{
return a.w < b.w;
}
int getfather(int i)
{
if(f[i] == i) return i;
else return f[i] = getfather(f[i]);
}
int main()
{
while(scanf("%d%d",&N,&M) && N)
{
edgenum = 0;
for(int i = 0; i < maxm; i++) f[i] = i;
for(int i = 0; i < N; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge[edgenum++] = node(a,b,c);
}
sort(edge,edge+edgenum,cmp);//Sort according to the rules of cmp
int num = 0,ans = 0;
bool  judge = false;
for(int i = 0; i < edgenum; i++)
{
int a = getfather(edge[i].from);
int b = getfather(edge[i].to);
if(a != b)
{
f[a] = b;
num ++;
ans += edge[i].w;
if(num == M-1)
{judge =  true;break;}
}
}
if(!judge) printf("?\n");
else printf("%d\n",ans);
}
return 0;
}```

Posted on Thu, 13 Feb 2020 12:10:28 -0800 by kannu