Uva 544 Solution

#include<bits/stdc++.h>
#define N 100000
#define p pair<int, pair<string, string>>
using namespace std;
map<string, string>parent;

bool compare(p A, p B)
{
    return A.first > B.first;
}

string check(string s)
{
    if(parent[s] == "")
        return s;

    return parent[s] = check(parent[s]);
}

int main()
{
    string c1, c2;
    int w, node, edge, i, x = 1;

    while(cin >> node >> edge && node != 0 && edge != 0)
    {
        vector<p>v;
        parent.clear();

        for(i=1;i<=edge;i++)
        {
            cin >> c1 >> c2 >> w;
            v.push_back(make_pair(w, make_pair(c1, c2)));
        }

        cin >> c1 >> c2;

        sort(v.begin(), v.end(), compare);

        int mn = N;

        for(i=0;i<v.size();i++)
        {
            string r1 = check(v[i].second.first);
            string r2 = check(v[i].second.second);

            if(r1 != r2)
            {
                parent[r1] = r2;

                if(mn > v[i].first)
                    mn = v[i].first;

                if(check(c1) == check(c2))
                    break;
            }
        }

        cout << "Scenario #" << x++ << "\n";
        cout << mn << " tons" << "\n\n";
    }

    return 0;
}