結果

問題 No.807 umg tours
ユーザー cidercider
提出日時 2019-03-22 23:07:24
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,657 bytes
コンパイル時間 1,713 ms
コンパイル使用メモリ 177,140 KB
実行使用メモリ 814,052 KB
最終ジャッジ日時 2023-10-19 10:20:10
合計ジャッジ時間 4,450 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

template<typename T>
void say(vector<T> s, char r) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << r << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("yes");
	else say("no");
}

void Yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

void YN(bool b) {
	if (b)say("YES");
	else say("NO");
}

template<typename T>
void maxi(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T& a, T b) {
	a = min(a, b);
}

void exact_say(double x) {
	cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
}

template<typename T>
vector<vector<T>> fill_vector(int h, int w, T val) {
	vector<vector<T>> ret;
	vector<T> v(w, val);
	rep(h)ret.push_back(v);
	return ret;
}

signed main() {
	makei(n);
	makei(m);
	vi ans(n, INT_MAX);
	vb used(n, false);
	vvi g = fill_vector(n, n, (ll)INT_MAX);
	rep(m) {
		makei(a);
		makei(b);
		makei(c);
		--a; --b;
		g[a][b] = c;
		g[b][a] = c;
	}
	ans[0] = 0;
	used[0] = true;
	rep(n) {
		mini(ans[i], ans[0] + g[0][i]);
	}
	while (true) {
		int v = -1;
		for (int u = 0; u < n; ++u) {
			if (!used[u] && (v == -1 || ans[u] < ans[v]))v = u;
		}
		if (v == -1)break;
		used[v] = true;
		rep(n) {
			mini(ans[i], ans[v] + g[v][i]);
		}
	}


	vi ans2(n, INT_MAX);
	rep(n)used[i] = false;
	ans2[0] = 0;
	used[0] = true;
	rep(n) {
		if (g[i][0] < INT_MAX) ans2[i] = 0;
	}
	while (true) {
		int v = -1;
		for (int u = 0; u < n; ++u) {
			if (!used[u] && (v == -1 || ans2[u] < ans2[v]))v = u;
		}
		if (v == -1)break;
		used[v] = true;
		rep(n) {
			mini(ans2[i], ans2[v] + g[v][i]);
			if (g[v][i] < INT_MAX)mini(ans2[i], ans[v]);
		}
	}
	rep(n)say(ans[i] + ans2[i]);
}
0