Submission #1841481


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 < roadsWithoutOrigin[i][j]) {
                    roadsWithoutOrigin[i][j] = dist;
                }
            }
        }
    }

    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 4095 Byte
Status WA
Exec Time 69 ms
Memory 1024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 20
WA × 13
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 19 ms 512 KB
subtask1_02.txt AC 16 ms 640 KB
subtask1_03.txt WA 41 ms 768 KB
subtask1_04.txt WA 2 ms 256 KB
subtask1_05.txt WA 9 ms 384 KB
subtask1_06.txt WA 40 ms 768 KB
subtask1_07.txt WA 5 ms 384 KB
subtask1_08.txt AC 4 ms 384 KB
subtask1_09.txt AC 38 ms 768 KB
subtask1_10.txt AC 18 ms 512 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 20 ms 640 KB
subtask1_13.txt WA 7 ms 384 KB
subtask1_14.txt AC 3 ms 256 KB
subtask1_15.txt AC 68 ms 1024 KB
subtask1_16.txt AC 49 ms 1024 KB
subtask1_17.txt WA 38 ms 1024 KB
subtask1_18.txt WA 54 ms 1024 KB
subtask1_19.txt WA 54 ms 1024 KB
subtask1_20.txt WA 43 ms 1024 KB
subtask1_21.txt AC 44 ms 1024 KB
subtask1_22.txt AC 65 ms 1024 KB
subtask1_23.txt AC 69 ms 1024 KB
subtask1_24.txt WA 42 ms 1024 KB
subtask1_25.txt AC 49 ms 1024 KB
subtask1_26.txt AC 58 ms 1024 KB
subtask1_27.txt AC 53 ms 1024 KB
subtask1_28.txt AC 38 ms 1024 KB
subtask1_29.txt AC 58 ms 1024 KB
subtask1_30.txt WA 35 ms 1024 KB