Submission #4639043
Source Code Expand
#include <bits/stdc++.h> #define INF 1e9 using namespace std; int N, M, R; int cost[201][201]; void warshall_floyd() { for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); } } } return; } int perm(vector<int> r) { sort(r.begin(), r.end()); int ans = INF; do { int sum = 0; for (int i = 0; i < R - 1; i++) { sum += cost[r[i]][r[i + 1]]; } ans = min(ans, sum); } while (next_permutation(r.begin(), r.end())); return ans; } int main() { cin >> N >> M >> R; vector<int> r(R); for (int i = 0; i < R; i++) { int town; cin >> town; r[i] = town - 1; } fill(cost[0], cost[200], INF); for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; cost[a][b] = c; cost[b][a] = c; } warshall_floyd(); cout << perm(r) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - joisino's travel |
User | nnsr |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1120 Byte |
Status | AC |
Exec Time | 25 ms |
Memory | 384 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 | 24 ms | 384 KB |
02.txt | AC | 11 ms | 384 KB |
03.txt | AC | 11 ms | 384 KB |
04.txt | AC | 12 ms | 384 KB |
05.txt | AC | 14 ms | 384 KB |
06.txt | AC | 24 ms | 384 KB |
07.txt | AC | 25 ms | 384 KB |
08.txt | AC | 10 ms | 384 KB |
sample_01.txt | AC | 1 ms | 384 KB |
sample_02.txt | AC | 1 ms | 384 KB |
sample_03.txt | AC | 1 ms | 384 KB |