#594489 (C++11) No.1320 Two Type Min Cost Cycle

提出ソース

結果

問題	No.1320 Two Type Min Cost Cycle
ユーザー	hirokazu1020
提出日時	2020-12-17 00:42:11
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	1,596 bytes
コンパイル時間	2,809 ms
コンパイル使用メモリ	111,344 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-20 05:37:25
合計ジャッジ時間	6,923 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	25 ms 5,376 KB
testcase_08	AC	36 ms 5,376 KB
testcase_09	WA	-
testcase_10	AC	32 ms 5,376 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	21 ms 5,376 KB
testcase_15	AC	34 ms 5,376 KB
testcase_16	WA	-
testcase_17	AC	14 ms 5,376 KB
testcase_18	AC	14 ms 5,376 KB
testcase_19	AC	57 ms 5,376 KB
testcase_20	AC	8 ms 5,376 KB
testcase_21	AC	162 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	1 ms 5,376 KB
testcase_28	AC	23 ms 5,376 KB
testcase_29	AC	42 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	9 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	3 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	WA	-
testcase_38	AC	2 ms 5,376 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	34 ms 5,376 KB
testcase_44	AC	18 ms 5,376 KB
testcase_45	AC	353 ms 5,376 KB
testcase_46	AC	7 ms 5,376 KB
testcase_47	AC	57 ms 5,376 KB
testcase_48	AC	59 ms 5,376 KB
testcase_49	AC	6 ms 5,376 KB
testcase_50	AC	2 ms 5,376 KB
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	AC	104 ms 5,376 KB
testcase_55	AC	104 ms 5,376 KB
testcase_56	AC	103 ms 5,376 KB
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-

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

ソースコード

raw source code

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()






int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	int n, m;
	cin >> t >> n >> m;
	vector<vector<pair<int, int>>> edge(n, vector<pair<int, int>>());
	rep(_, m) {
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		edge[u].emplace_back(v, w);
		if (t == 0)edge[v].emplace_back(u, w);
	}
	rep(i, n) {
		sort(all(edge[i]));
	}

	long long ans = 1LL << 60;
	rep(i, n) {
		vector<long long> d(n, 1LL << 60);
		d[i] = 0;
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
		pq.emplace(0, i);

		while (!pq.empty()) {
			auto pa = pq.top();
			pq.pop();
			if (d[pa.second] < pa.first)continue;

			for (auto e : edge[pa.second]) {
				int v = e.first;
				int w = e.second;
				if (pa.first + w < d[v]) {
					d[v] = pa.first + w;
					pq.emplace(d[v], v);
				}
			}
		}
		rep(j, n) {
			for (auto e: edge[j]) {
				if (e.first == i && d[j] != e.second) {
					ans = min(ans, d[j] + e.second);
				}
			}
		}
	}

	if (ans == (1LL << 60))ans = -1;
	cout << ans << endl;


	return 0;
}

yukicoder

結果

テストケース

ソースコード