結果
問題 | No.114 遠い未来 |
ユーザー | anta |
提出日時 | 2014-12-29 00:43:49 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,766 ms / 5,000 ms |
コード長 | 3,138 bytes |
コンパイル時間 | 765 ms |
コンパイル使用メモリ | 96,148 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-13 00:09:29 |
合計ジャッジ時間 | 14,879 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
6,816 KB |
testcase_01 | AC | 974 ms
6,944 KB |
testcase_02 | AC | 1,766 ms
6,940 KB |
testcase_03 | AC | 166 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 4 ms
6,940 KB |
testcase_06 | AC | 1,637 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 6 ms
6,940 KB |
testcase_10 | AC | 109 ms
6,940 KB |
testcase_11 | AC | 321 ms
6,944 KB |
testcase_12 | AC | 976 ms
6,940 KB |
testcase_13 | AC | 969 ms
6,944 KB |
testcase_14 | AC | 1,729 ms
6,940 KB |
testcase_15 | AC | 1,209 ms
6,940 KB |
testcase_16 | AC | 893 ms
6,940 KB |
testcase_17 | AC | 919 ms
6,944 KB |
testcase_18 | AC | 977 ms
6,940 KB |
testcase_19 | AC | 431 ms
6,940 KB |
testcase_20 | AC | 124 ms
6,940 KB |
testcase_21 | AC | 33 ms
6,940 KB |
testcase_22 | AC | 29 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,944 KB |
testcase_24 | AC | 3 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 1 ms
6,940 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | scanf("%d%d%d", &N, &M, &T); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:49:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 49 | scanf("%d%d%d", &a, &b, &c), -- a, -- b; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 59 | scanf("%d", &v), -- v; | ~~~~~^~~~~~~~~~
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <cassert> #include <limits> #include <functional> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll; typedef vector<string> vs; typedef long double ld; template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; } int main() { int N, M, T; scanf("%d%d%d", &N, &M, &T); vector<vector<int> > g(N, vector<int>(N, INF)); rep(i, N) g[i][i] = 0; rep(i, M) { int a, b, c; scanf("%d%d%d", &a, &b, &c), -- a, -- b; amin(g[a][b], c); amin(g[b][a], c); } rep(k, N) rep(i, N) rep(j, N) amin(g[i][j], g[i][k] + g[k][j]); vi required(T); vector<bool> important(N, false); rep(i, T) { int v; scanf("%d", &v), -- v; required[i] = v; important[v] = true; } if(T == 1) { puts("0"); return 0; } vi steiners; rep(i, N) if(!important[i]) steiners.push_back(i); int X = steiners.size(); int ans = INF; if(T >= 16) { vector<int> vertices; rep(use, 1 << X) { vertices = required; rep(i, X) if(use >> i & 1) vertices.push_back(steiners[i]); int V = vertices.size(); vector<bool> vis(V, false); vector<int> cost(V, INF); int totalcost = 0; cost[0] = 0; rep(k, V) { pii p(INF, -1); rep(i, V) if(!vis[i]) amin(p, mp(cost[i], i)); int i = p.second, v = vertices[i]; vis[i] = true; totalcost += cost[i]; rep(j, V) amin(cost[j], g[v][vertices[j]]); } amin(ans, totalcost); } }else { const short INFS = 0x3f3f; vector<short> dp((1 << T) * N, INFS); rep(p, T) rep(q, N) dp[(1 << p) * N + q] = g[required[p]][q]; rep(S, 1 << T) { if(!(S & (S-1))) continue; rep(p, N) { short x = INFS; for(int E = (S-1) & S; E > 0; (-- E) &= S) amin(x, dp[E * N + p] + dp[(S - E) * N + p]); dp[S * N + p] = x; } rep(p, N) { short x = INFS; rep(q, N) amin(x, dp[S * N + q] + g[p][q]); dp[S * N + p] = x; } } int U = (1 << T) - 1; rep(S, 1 << T) rep(q, N) amin(ans, dp[S * N + q] + dp[(U - S) * N + q]); } printf("%d\n", ans); return 0; }