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

提出ソース

結果

問題	No.114 遠い未来
ユーザー	shimomire
提出日時	2014-12-29 02:38:38
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	7,978 bytes
コンパイル時間	1,623 ms
コンパイル使用メモリ	145,228 KB
実行使用メモリ	14,008 KB
最終ジャッジ日時	2024-06-13 00:50:06
合計ジャッジ時間	15,674 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	219 ms 6,812 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	127 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	15 ms 6,940 KB
testcase_06	AC	2,274 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	26 ms 6,944 KB
testcase_10	AC	1,356 ms 6,944 KB
testcase_11	TLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-

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

ソースコード

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)];
    }
};

// Cost kruskal(Graph g){
// 	const int V=g.size();
// 	UnionFind uf=UnionFind(V);
// 	priority_queue<Edge,vector<Edge>,greater<Edge>> que;
// 	REP(u,V)for(Edge e:g[u])que.push(e);
// 	Cost res=0;
// 	while(!que.empty()){
// 		Edge e=que.top();que.pop();
// 		if(!uf.same(e.from,e.to)){
// 			uf.unite(e.from,e.to);
// 			res+=e.cost;
// 		}
// 	}
// 	return res;
// }

class Main{

	typedef ll Cost;

	int bit_count(int v){
		int res=0;while(v!=0){if(v%2)res++;v/=2;}return res;
	}
	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<ll>(n,INF<Cost>()));
		

		REP(i,ts.size())REP(p,n){
			REP(q,n) dp[1<<i][p]=min(dp[1<<i][p],ds[p][q]+ds[ts[i]][q]);
		}
		REP(i,ts.size())REP(j,ts.size())REP(p,n)REP(q,n){
			dp[(1<<i | 1<< j)][p]=min(dp[(1<<i | 1<< j)][p],ds[p][q]+ds[ts[i]][q]+ds[ts[j]][q]);
		}

		// // trivial case
		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)REP(E,S)if((E|S) == 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);

		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));
		}
		vector<int> vs(T);REP(i,T){cin >> vs[i];vs[i]--;}
		sort(ALL(vs));

		vector<int> unused;
		{
			int vi=0;
			REP(i,N)if(vi<T){
				if(vs[vi]!=i)unused.push_back(i);
				else vi++;
			}
		}

		map<int,int> unusedind;
		REP(i,unused.size())unusedind[unused[i]]=i;


		if(T>=14){
			//N-T<=21
			// 最小全域木

			ll mv=INF<ll>();

			vector<Edge> es;REP(u,N)for(Edge e:g[u])es.push_back(e);
			sort(ALL(es));
			REP(bit,1<<(N-T)){
				UnionFind uf=UnionFind(N);
				Cost res=0;
				for(Edge& e:es)if(!unusedind.count(e.from) || bit&(1<<(unusedind[e.from])))if(!unusedind.count(e.to) || bit&(1<<(unusedind[e.to]))){						
					if(!uf.same(e.from,e.to)){
						uf.unite(e.from,e.to);
						res+=e.cost;
					}	
				}
				mv=min(mv,res);
			}
			cout << mv <<endl;
		}else{
			// T <=13
			//シュタイナー木
			vector<vector<ll>> mat(N,vector<ll>(N,INF<ll>()));
			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

結果

テストケース

ソースコード