結果

問題 No.114 遠い未来
ユーザー shimomireshimomire
提出日時 2014-12-29 05:05:08
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 8,142 bytes
コンパイル時間 1,971 ms
コンパイル使用メモリ 142,748 KB
実行使用メモリ 17,636 KB
最終ジャッジ日時 2023-09-03 20:01:32
合計ジャッジ時間 9,980 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 810 ms
4,384 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
	}

	class subset{
		private:
		struct Iter{
			int v,bit;
			int operator*(){
				int res=0,vi=0;
				REP(bi,32)if(bit & (1<<bi)){
					if(v&(1<<vi))res+=1<<bi;
					vi++;
				}
				return res;
			}
			bool operator!=(Iter& itr) {return v < itr.v;}
			void operator++(){++v;}
		};
		Iter i, n;
		public:
		subset(int bit){
			i={0,bit};n={1<<(__builtin_popcount(bit)),bit};
		}
		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<ll>(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(int 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);

		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>=16){
			//N-T<=19
			// 最小全域木

			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 <=15
			//シュタイナー木
			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;
}
0