SRM492 Div2 Hard(1000) TimeTravellingSalesman

TimeTravellingSalesman

巡回セールスマンだけど単なる最小全域木。

#include <string>
#include <vector>
#include <numeric>
#include <sstream>
using namespace std;

class TimeTravellingSalesman{public:
long long determineCost( int N, vector <string> roads )
{
    string s = accumulate( roads.begin(), roads.end(), string() );
    stringstream ss(s);
    vector<int> a, b, c;
    int ta, tb, tc; char t;
    int n = 0;
    while ( ss>>ta>>t>>tb>>t>>tc )
        a.push_back( ta ),
        b.push_back( tb ),
        c.push_back( tc ),
        n++;

    vector<bool> visit( N );
    visit[0] = true;
    int ans = 0;

    while ( true )
    {
        int e = -1;
        for ( int i=0; i<(int)n; i++ )
            if ( visit[a[i]] ^ visit[b[i]]  &&
                 ( e == -1  ||  c[i] < c[e] ) )
                e = i;
        if ( e == -1 )
            break;
        visit[a[e]] = visit[b[e]] = true;
        ans += c[e];
    }

    for ( int i=0; i<N; i++ )
        if ( ! visit[i] )
            ans = -1;
    return ans;
}};