結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー mukadenodaiou
提出日時 2018-04-06 11:59:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,236 bytes
コンパイル時間 1,316 ms
コンパイル使用メモリ 113,876 KB
実行使用メモリ 10,400 KB
最終ジャッジ日時 2024-06-26 10:45:16
合計ジャッジ時間 8,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int N = 1000000;
const int mod = 1000000007;
const int INF = 1 << 30;
#define rep(i,n) for(ll i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
#define pb push_back
ll ppow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if ((n & 1) == 1)ans = ans * x;
		x = x * x;
		n >>= 1;
		x %= mod;
		ans %= mod;
	}
	return ans;
}
string YN(bool b) { return(b ? "YES" : "NO"); }
string yn(bool b) { return(b ? "Yes" : "No"); }
ll sz, fact[N], inv[N];
void setinv() {
	fact[0] = 1; inv[0] = 1;
	for (int i = 1; i <= sz; i++) {
		fact[i] = (fact[i - 1] * i) % mod;  //階乗を求める
		inv[i] = ppow(fact[i], (ll)mod - 2) % mod; // フェルマーの小定理で逆元を求める
	}
}
ll conv(ll r) {//nCr
	return fact[sz] * inv[r] % mod * inv[sz - r] % mod;
}
struct  edge { ll to; ll cost; };
ll n, s[100], m, mn = INF;
vector<edge> e[50];
void dfs(ll pos, ll cost, bitset<50>b2) {
	priority_queue<ll, vector<ll>, greater<ll>>q;
	if (cost >= mn)return;
	if (pos == n - 1) {
		//cout << b2 << endl;
		ll c = cost;
		ll mnc = INF;
		for (int i = 1; i < n; ++i)if (b2[i])q.push(s[i]);
		if (q.size() == 0)return;
		c += q.top(); q.pop();
		if (q.size() >= 1) {
			ll a = 0;
			a += q.top();
			mnc = min(mnc, a);
		}
		rep(i, e[n - 1].size()) {
			if (!b2[e[n - 1][i].to])mnc = min(s[e[n - 1][i].to] + 2 * e[n - 1][i].cost, mnc);
		}
		c += mnc;
		mn = min(mn, c);
		return;
	}
	bitset<50>b = b2;
	b[pos] = 1;
	rep(i, e[pos].size()) {
		if (!b[e[pos][i].to])dfs(e[pos][i].to, e[pos][i].cost+cost, b);
	}
}
int main() {
	cin >> n;
	rep(i, n)cin >> s[i];
	cin >> m;
	ll a, b, c;
	rep(i, m) {
		cin >> a >> b >> c;
		e[a].push_back(edge{ b,c });
		e[b].push_back(edge{ a,c });
	}
	bitset<50>bi = {};
	dfs(0, 0, bi);
	cout << mn << endl;
	return 0;
}
0