Country Roads Solution
#include<bits/stdc++.h>
#define N 600
#define pii pair<int, int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
struct str
{
int u, v, w;
};
vector<str>v, graph;
int parent[N], dis[N];
vector<pii>a[N];
bool compare(str a, str b)
{
return a.w < b.w;
}
int finds(int x)
{
if(parent[x] < 0)
return x;
return parent[x] = finds(parent[x]);
}
int unions(int a, int b, int w)
{
int u = finds(a);
int v = finds(b);
if(u == v)
return 0;
else
{
if(parent[u] <= parent[v])
{
parent[u] += parent[v];
parent[v] = u;
}
else
{
parent[v] += parent[u];
parent[u] = v;
}
return w;
}
}
void mst(int node)
{
for(int i=0; i<=node; i++)
parent[i] = -1;
sort(v.begin(), v.end(), compare);
int cnt = 0;
for(int i=0; i<v.size(); i++)
{
int s = unions(v[i].u, v[i].v, v[i].w);
if(s > 0)
{
cnt++;
graph.push_back(v[i]);
}
if(cnt == node-1)
break;
}
}
void dfs(int from, int node, int mx, int w)
{
mx = max(mx, w);
dis[node] = mx;
for(auto i : a[node])
{
if(i.first == from)
continue;
dfs(node, i.first, mx, i.second);
}
}
void clears()
{
v.clear(), graph.clear();
for(int i=0; i<N; i++)
parent[i] = dis[i] = 0, a[i].clear();
}
int main()
{
fast
int t, k = 1;
cin >> t;
while(t--)
{
int n, m, x, y, w, s;
cin >> n >> m;
for(int i=1; i<=m; i++)
{
cin >> x >> y >> w;
v.push_back({x, y, w});
}
mst(n);
for(int i=0; i<graph.size(); i++)
{
x = graph[i].u;
y = graph[i].v;
w = graph[i].w;
a[x].push_back(pii(y, w));
a[y].push_back(pii(x, w));
}
cin >> s;
dfs(s, s, -1, -1);
cout << "Case " << k++ << ":\n";
for(int i=0; i<n; i++)
{
if(s == i)
cout << 0 << "\n";
else if(dis[i] == 0)
cout << "Impossible" << "\n";
else
cout << dis[i] << "\n";
}
clears();
}
return 0;
}
Comments
Post a Comment