Submission #1841472
Source Code Expand
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>
using namespace std;
#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<vector<vector<int> > > vvvi;
typedef vector<string> vs;
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec){
os << "[";
for(int i = 0; i < vec.size(); i++){
os << vec[i] << ",";
}
os << "]";
return os;
}
template<typename T>
T input(){
T t;
cin >> t;
return t;
}
template<typename T>
vector<T> input(const int N){
vector<T> v(N);
repeat(i,N) cin >> v[i];
return v;
}
long long gcd(long long a, long long b){
if(b == 0){
return a;
}
return gcd(b, a % b);
}
long long lcm(long long a, long long b){
return (a / gcd(a, b)) * b;
}
long long mul(const long long& a, const long long& b, const long long& mod) {
return ((a % mod) * (b % mod)) % mod;
}
long long power(const long long& x, const long long& y, const long long& mod) {
if (y == 0) {
return 1;
} else if (y == 1) {
return x % mod;
} else {
long long value = power(x, y / 2, mod);
if (y % 2 == 0) {
return mul(value, value, mod);
} else {
return mul(value, value, mod) * x % mod;
}
}
}
long long div(const long long& a, const long long& b, const long long& mod) {
return mul(a, power(b, mod - 2, mod), mod);
}
map<long long, long long> factorials;
long long factorial(const long long& n, const long long& mod) {
if (n == 0 || n == 1) {
return 1;
}
if (factorials[n] != 0) {
return factorials[n];
}
factorials[n] = n * factorial(n - 1, mod) % mod;
return factorials[n] % mod;
}
long long combination(const long long& n, const long long& x, const long long& mod) {
long long numerator = 1;
long long denominator = 1;
repeat(i, x) {
numerator *= (n - i) % mod;
numerator %= mod;
denominator *= (i + 1) % mod;
denominator %= mod;
}
return div(numerator, denominator, mod);
}
struct Node {
int totalLength;
int currentHouse;
Node(int _totalLength, int _currentHouse) {
totalLength = _totalLength;
currentHouse = _currentHouse;
}
bool operator >(const Node& lhs) const {
return this->totalLength > lhs.totalLength;
}
};
int main(){
int N, M;
int NO_CONNECTION = 10000000;
cin >> N >> M;
vvi roads(N, vi(N, NO_CONNECTION));
int origin, destination, length;
repeat (i, M) {
cin >> origin >> destination >> length;
roads[origin - 1][destination - 1] = length;
roads[destination - 1][origin - 1] = length;
}
vvi roadsWithoutOrigin = roads;
repeat (i, N) {
roadsWithoutOrigin[0][i] = NO_CONNECTION;
roadsWithoutOrigin[i][0] = NO_CONNECTION;
}
repeat (i, N) {
repeat (j, N) {
repeat (k, N) {
int dist = roadsWithoutOrigin[i][k] + roadsWithoutOrigin[k][j];
if (dist < NO_CONNECTION) {
roadsWithoutOrigin[i][j] = min(dist, roadsWithoutOrigin[i][j]);
}
}
}
}
int minimum = NO_CONNECTION;
for (int i = 1; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
minimum = min(minimum, roadsWithoutOrigin[i][j] + roads[0][i] + roads[j][0]);
}
}
if (minimum < NO_CONNECTION) {
cout << minimum << endl;
} else {
cout << -1 << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Blue Bird |
User |
xeonics |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
4115 Byte |
Status |
WA |
Exec Time |
135 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
WA |
37 ms |
512 KB |
subtask1_02.txt |
AC |
30 ms |
640 KB |
subtask1_03.txt |
WA |
80 ms |
768 KB |
subtask1_04.txt |
WA |
2 ms |
256 KB |
subtask1_05.txt |
WA |
17 ms |
384 KB |
subtask1_06.txt |
WA |
67 ms |
768 KB |
subtask1_07.txt |
WA |
7 ms |
384 KB |
subtask1_08.txt |
AC |
4 ms |
384 KB |
subtask1_09.txt |
AC |
58 ms |
768 KB |
subtask1_10.txt |
AC |
32 ms |
512 KB |
subtask1_11.txt |
AC |
1 ms |
256 KB |
subtask1_12.txt |
AC |
31 ms |
640 KB |
subtask1_13.txt |
WA |
9 ms |
384 KB |
subtask1_14.txt |
AC |
4 ms |
384 KB |
subtask1_15.txt |
AC |
109 ms |
1024 KB |
subtask1_16.txt |
AC |
104 ms |
1024 KB |
subtask1_17.txt |
WA |
59 ms |
1024 KB |
subtask1_18.txt |
WA |
128 ms |
1024 KB |
subtask1_19.txt |
WA |
124 ms |
1024 KB |
subtask1_20.txt |
WA |
77 ms |
1024 KB |
subtask1_21.txt |
AC |
80 ms |
1024 KB |
subtask1_22.txt |
AC |
118 ms |
1024 KB |
subtask1_23.txt |
AC |
106 ms |
1024 KB |
subtask1_24.txt |
WA |
76 ms |
1024 KB |
subtask1_25.txt |
AC |
107 ms |
1024 KB |
subtask1_26.txt |
AC |
134 ms |
1024 KB |
subtask1_27.txt |
AC |
135 ms |
1024 KB |
subtask1_28.txt |
AC |
66 ms |
1024 KB |
subtask1_29.txt |
AC |
133 ms |
1024 KB |
subtask1_30.txt |
WA |
41 ms |
1024 KB |