Submission #6907915
Source Code Expand
Copy
#include <bits/stdc++.h> #define int long long #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define DEC(i, a, b) for (int i = (a); i > (b); --i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define pb push_back #define ALL(obj) (obj).begin(), (obj).end() #define debug(x) cerr << #x << ": " << x << '\n' using namespace std; typedef long long ll; const int INF = (int)1e9; const int MOD = (int)1e9 + 7; const ll LINF = (int)1e18; const double EPS = 1e-9; const int MAX_V = (int)200; int d[MAX_V][MAX_V]; // d[u][v]は辺(u,v)のコスト。0-origin. 初期化忘れずに int V; void warshall_floyd() { REP(k, V) REP(i, V) REP(j, V) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int M,R; cin >> V >> M >> R; vector<int> r(R); REP(i,R) { cin >> r[i]; --r[i]; } sort(ALL(r)); // 初期化 REP(i, V) { fill(d[i], d[i] + V, LINF); d[i][i] = 0; } // コスト入力 REP(i,M) { int a,b,c; cin >> a >> b >> c; --a; --b; // 有向・無向の区別注意 d[a][b] = c; d[b][a] = c; } warshall_floyd(); int ans = LINF; do { int tmp = 0; REP(i,R-1) tmp += d[r[i]][r[i+1]]; ans = min(ans,tmp); } while (next_permutation(ALL(r))); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - joisino's travel |
User | aximov |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1402 Byte |
Status | AC |
Exec Time | 16 ms |
Memory | 640 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 16 ms | 640 KB |
02.txt | AC | 11 ms | 640 KB |
03.txt | AC | 11 ms | 640 KB |
04.txt | AC | 12 ms | 640 KB |
05.txt | AC | 12 ms | 640 KB |
06.txt | AC | 15 ms | 512 KB |
07.txt | AC | 16 ms | 640 KB |
08.txt | AC | 10 ms | 512 KB |
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |