#7895 (C++11) No.114 遠い未来

提出ソース

結果

問題	No.114 遠い未来
ユーザー	shimomire
提出日時	2014-12-29 06:40:54
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2,010 ms / 5,000 ms
コード長	7,509 bytes
コンパイル時間	1,467 ms
コンパイル使用メモリ	134,544 KB
実行使用メモリ	13,184 KB
最終ジャッジ日時	2024-06-13 01:00:04
合計ジャッジ時間	13,043 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	26 ms 5,248 KB
testcase_01	AC	1,311 ms 13,184 KB
testcase_02	AC	300 ms 5,376 KB
testcase_03	AC	55 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	4 ms 5,376 KB
testcase_06	AC	706 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	6 ms 5,376 KB
testcase_10	AC	125 ms 5,760 KB
testcase_11	AC	396 ms 8,192 KB
testcase_12	AC	1,291 ms 13,184 KB
testcase_13	AC	1,276 ms 13,056 KB
testcase_14	AC	719 ms 5,376 KB
testcase_15	AC	2,010 ms 5,376 KB
testcase_16	AC	342 ms 5,376 KB
testcase_17	AC	423 ms 5,376 KB
testcase_18	AC	1,406 ms 5,376 KB
testcase_19	AC	176 ms 5,376 KB
testcase_20	AC	165 ms 5,376 KB
testcase_21	AC	13 ms 5,376 KB
testcase_22	AC	16 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	1 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>// c
#include <iostream>// io
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>// container
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <algorithm>// other
#include <complex>
#include <numeric>
#include <functional>
#include <random>
#include <regex>
using namespace std;

using i32=int32_t;using i64=int64_t;using ll =i64;using uint=uint32_t;using ull=uint64_t;
template<typename T> using matrix=vector<vector<T> >;

#define ALL(c) (begin(c)),(end(c))
#define REP(i,n) FOR(i,0,n)
#define REPr(i,n) FORr(i,0,n)
#define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define FORr(i,l,r) for(int i=(int)(r)-1;i>=(int)(l);--i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end())
//debug
#define DUMP(x)  cerr << #x << " = " << (x)
#define LINE()    cerr<< " (L" << __LINE__ << ")"

class range {
private:
	struct Iter{
		int v;
		int operator*(){return v;}
		bool operator!=(Iter& itr) {return v < itr.v;}
		void operator++() {++v;}
	};
	Iter i, n;
public:
	range(int n) : i({0}), n({n}) {}
	range(int i, int n) : i({i}), n({n}) {}
	Iter& begin() {return i;}
	Iter& end() {return n;}
};

//output
template<typename T> ostream& operator << (ostream& os, const vector<T>& as){REP(i,as.size()){if(i!=0)os<<" "; os<<as[i];}return os;}
template<typename T> ostream& operator << (ostream& os, const vector<vector<T>>& as){REP(i,as.size()){if(i!=0)os<<endl; os<<as[i];}return os;}
template<typename T> ostream& operator << (ostream& os, const set<T>& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os<<a;}return os;}
template<typename T1,typename T2> ostream& operator << (ostream& os, const pair<T1,T2>& p){os<<p.first<<" "<<p.second;return os;}
template<typename K,typename V> ostream& operator << (ostream& os, const map<K,V>& m){bool isF=true;for(auto& p:m){if(!isF)os<<endl;os<<p;isF=false;}return os;}
template<typename T1> ostream& operator << (ostream& os, const tuple<T1>& t){os << get<0>(t);return os;}
template<typename T1,typename T2> ostream& operator << (ostream& os, const tuple<T1,T2>& t){os << get<0>(t)<<" "<<get<1>(t);return os;}
template<typename T1,typename T2,typename T3> ostream& operator << (ostream& os, const tuple<T1,T2,T3>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5,T6>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t)<<" "<<get<5>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> ostream& operator << (ostream& os, const tuple<T1,T2,T3,T4,T5,T6,T7>& t){os << get<0>(t)<<" "<<get<1>(t)<<" "<<get<2>(t)<<" "<<get<3>(t)<<" "<<get<4>(t)<<" "<<get<5>(t)<<" "<<get<6>(t);return os;}

//input
char tmp[1000];
#define nextInt(n) scanf("%d",&n)
#define nextLong(n) scanf("%lld",&n) //I64d
#define nextDouble(n) scanf("%lf",&n) 
#define nextChar(n) scanf("%c",&n)
#define nextString(n) scanf("%s",tmp);n=tmp

// values
template<typename T> T INF(){assert(false);};
template<> int INF<int>(){return 1<<28;};
template<> ll INF<ll>(){return 1LL<<58;};
template<> double INF<double>(){return 1e16;};

template<class T> T EPS(){assert(false);};
template<> int EPS<int>(){return 1;};
template<> ll EPS<ll>(){return 1LL;};
template<> double EPS<double>(){return 1e-8;};
template<> long double EPS<long double>(){return 1e-8;};

template<typename T,typename U> T pfmod(T v,U M){return fmod(fmod(v,M)+M,M);}

ll gcd_positive(ll a,ll b) { return b == 0 ? a : gcd_positive(b,a%b); }
ll gcd(ll a,ll b) { return gcd_positive(abs(a), abs(b)); }
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

namespace EGraph{
	typedef ll Cost;Cost CINF=INF<Cost>();
	struct Edge{
		int from,to;Cost cost;
		Edge(int from,int to,Cost cost)
		: from(from),to(to),cost(cost) {};
		bool operator<(Edge r) const{ return cost<r.cost;}
		bool operator>(Edge r) const{ return cost>r.cost;}
	};
	typedef vector<vector<Edge> >  Graph;
}
using namespace EGraph;

struct UnionFind{
    vector<int> par,rank,ss;
    int size;
    UnionFind(int n){
        REP(i,n) par.push_back(i);
        rank = vector<int>(n);ss=vector<int>(n,1);size=n;
    }
    int root(int x){
        if(par[x] == x)return x;
        return par[x] = root(par[x]);
    }
    bool same(int x,int y){
        return root(x) == root(y);
    }
    void unite(int x,int y){
        x = root(x);y = root(y);if(x==y)return;
        if(rank[x]>rank[y])swap(x,y);
        par[x] = y;ss[y]+=ss[x];
        if(rank[x] == rank[y]) rank[x]++;
        size--;
    }
    int getS(int x){
        return ss[root(x)];
    }
};


class Main{

	typedef ll Cost;

	// E ⊂ S
	class subset{
		private:
		struct Iter{
			ull E,S;bool isF;
			ull operator*(){return E;}
			bool operator!=(Iter& itr) {return E != itr.E || isF != itr.isF;}
			void operator++(){
				E=(E-1)&S;isF=false;
			}
		};
		Iter i, n;
		public:
		subset(ull S){
			i={S,S,true};n={S,S,false};
		}
		Iter& begin() {return i;}
		Iter& end() {return n;}
	};

	Cost minimum_steiner_tree(const vector<int>& ts, const vector<vector<Cost>> &g) {
		const int n = g.size();
		if (ts.size() <= 1) return 0;
		// all-pair shortest
		vector<vector<Cost>> ds=g;REP(k,n)REP(i,n)REP(j,n) ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);

		vector<vector<Cost>> dp(1<<ts.size(),vector<Cost>(n,INF<Cost>()));
		REP(i,ts.size())REP(q,n) dp[1 << i][q] = ds[ts[i]][q];
		
		REP(S,1<<ts.size())if(S & (S-1)){
			REP(p,n)for(ull E :subset(S)) dp[S][p]=min(dp[S][p],dp[E][p] + dp[S-E][p]);

			REP(p,n)REP(q,n) dp[S][p] = min(dp[S][p], dp[S][q] + ds[p][q] );
		}
		Cost res =INF<Cost>();REP(q,n)res = min(res,dp[((1 << ts.size())-1)][q]);
		return res;
	}

	public:
	void run(){
		int N,M,T;cin >> N >> M >> T;
		Graph g = Graph(N);
		vector<Edge> es;
		REP(i,M){
			int a,b,c;cin >> a >> b >> c;a--;b--;
			g[a].push_back(Edge(a,b,c));
			g[b].push_back(Edge(b,a,c));
			es.push_back(Edge(a,b,c));
		}
		vector<int> vs(T);REP(i,T){cin >> vs[i];vs[i]--;}
		ull must=0;REP(i,T)must+=1ULL<<vs[i];
		
		ull opt=((1ULL<<N) -1) - must;
		
		if(T>=16){
			//N-T<=19
			// 最小全域木
			sort(ALL(es));
			ll mv=INF<ll>();
			for(ull bit : subset(opt)){
				UnionFind uf=UnionFind(N);
				ull use=must | bit;
				Cost res=0;
				for(Edge& e:es)if((use & (1ULL<<e.from)) && (use &(1ULL<<e.to))){
					if(!uf.same(e.from,e.to)){
						uf.unite(e.from,e.to);
						res+=e.cost;
					}
				}
				bool ok=true;REP(i,vs.size())if(!uf.same(vs[0],vs[i]))ok=false;
				if(ok)mv=min(mv,res);
			}
			cout << mv <<endl;
		}else{
			// T <=15
			//シュタイナー木
			vector<vector<Cost>> mat(N,vector<Cost>(N,INF<Cost>()));
			REP(i,N)mat[i][i]=0;
			REP(i,N)EACH(e,g[i])mat[e->from][e->to]=e->cost;

			cout << minimum_steiner_tree(vs,mat) <<endl;
		}
	}
};

int main(){
	cout <<fixed<<setprecision(20);
	cin.tie(0);
	ios::sync_with_stdio(false);
	Main().run();
	return 0;
}

yukicoder

結果

テストケース

ソースコード