Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 10793

Autor: Guilherme Andrade

Código:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <map>
#include <climits>
#include <set>
#include <string>
#include <sstream>
#define FOR(i,a,b) for(__typeof(b) i=a; i<(b); ++i)
#define FOR0(i,b) for(__typeof(b) i=0; i<(b); ++i)
#define TRAV(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef vector<vi> vii;
typedef long long ll;

const int oo = INT_MAX;
int n;
vector< vector<pii> > adj;

class comp{
public:
        bool operator()(const pii& a, const pii& b){
                return a.second > b.second;
        }
};

void dijkstra(int src, vi& dist){
        dist.clear(); dist.assign(n+10,oo);
        vb visi(n+10);
        dist[src] = 0;
        priority_queue<pii, vector<pii>, comp> q;
        q.push(make_pair(src, dist[src]));

        while (true) {
                while (true) {
                        if(q.empty()) return;
                        if(!visi[q.top().first]) break;
                        q.pop();
                }

                pii top = q.top(); q.pop();
                visi[top.first] = true;

                TRAV(it, adj[top.first]){
                        if(!visi[it->first] && top.second + it->second < dist[it->first]){
                                dist[it->first] = top.second + it->second;
                                q.push(make_pair(it->first, dist[it->first]));
                        }
                }
        }
}

int main(){
        ios::sync_with_stdio(false);
        int t; cin >> t;
        FOR(test, 1, t+1) {
                int m; cin >> n >> m;
                adj.clear(); adj.resize(n+10);
                FOR0(i, m){
                        int x,y,w; cin >> x >> y >> w;
                        --x; --y;
                        adj[x].push_back(make_pair(y, w));
                        adj[y].push_back(make_pair(x, w));
                }

                vii dists(7);
                FOR0(i, 5) dijkstra(i, dists[i]);

                int ans = oo;
                FOR(i, 5, n){
                        bool equal = true;
                        int aux = dists[0][i];
                        FOR(j, 1, 5) {
                                if( dists[j][i] != aux ) { equal=false; break; }
                        }
                        if(equal){
                                vi dist;
                                dijkstra(i, dist);
                                ans = min( ans, *max_element(dist.begin(), dist.begin() + n) );
                        }
                }

                cout << "Map " << test << ": " << (ans == oo ? -1 : ans) << "\n";
        }
        return 0;
}