結果

問題 No.17 2つの地点に泊まりたい
ユーザー mai(舞葉)
提出日時 2017-05-17 23:03:03
言語 C++17(1z)
(gcc 7.2.0)
結果
AC  
実行時間 13 ms
コード長 4,193 Byte
コンパイル時間 2,041 ms
使用メモリ 2,856 KB
最終ジャッジ日時 2018-01-14 06:04:29

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 12 ms
2,852 KB
02.txt AC 12 ms
2,844 KB
03.txt AC 13 ms
2,848 KB
04.txt AC 13 ms
2,852 KB
05.txt AC 11 ms
2,852 KB
06.txt AC 12 ms
2,844 KB
07.txt AC 12 ms
2,856 KB
08.txt AC 12 ms
2,848 KB
09.txt AC 13 ms
2,844 KB
10.txt AC 13 ms
2,848 KB
99_system_test1.txt AC 13 ms
2,844 KB
challenge01.txt AC 12 ms
2,852 KB
system_test1.txt AC 12 ms
2,844 KB
system_test2.txt AC 12 ms
2,844 KB
system_test3.txt AC 12 ms
2,856 KB
system_test4.txt AC 12 ms
2,848 KB
system_test5.txt AC 12 ms
2,848 KB
system_test6.txt AC 12 ms
2,852 KB
system_test7.txt AC 12 ms
2,844 KB
system_test8.txt AC 12 ms
2,852 KB
system_test9.txt AC 12 ms
2,856 KB
system_test10.txt AC 13 ms
2,856 KB
system_test11.txt AC 13 ms
2,852 KB
system_test12.txt AC 12 ms
2,844 KB
system_test13.txt AC 12 ms
2,852 KB
system_test14.txt AC 12 ms
2,848 KB
テストケース一括ダウンロード

ソースコード

diff #
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define repeat(l) for(auto cnt=0;cnt<(l);++cnt)
#define upto(l,r) for(auto cnt=l;cnt<=r;++cnt)
#define downto(r,l) for(auti cnt=r;cnt>=l;--cnt)
#define BIGINT 0x7FFFFFFF
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
template<typename T1, typename T2>
ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }

#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())
namespace {
    std::chrono::system_clock::time_point ttt;
    void tic() { ttt = TIME; }
    void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); }
    std::chrono::system_clock::time_point tle = TIME;
#ifdef __MAI
    void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }
#else
#define safe_tle(k) ;
#endif
}

#ifdef __MAI //_getchar_nolock
#define getchar_unlocked getchar
#endif
namespace {
    class MaiScanner {
    public:
        template<typename T>
        void input_integer(T& var) {
            var = 0;
            T sign = 1;
            int cc = getchar_unlocked();
            for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
                if (cc == '-') sign = -1;
            for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
                var = (var << 3) + (var << 1) + cc - '0';
            var = var*sign;
        }
        inline int c() { return getchar_unlocked(); }
        inline MaiScanner& operator>>(int& var) {
            input_integer<int>(var);
            return *this;
        }
        inline MaiScanner& operator>>(long long& var) {
            input_integer<long long>(var);
            return *this;
        }
    };
}
MaiScanner scanner;


// 隣接行列を保持するグラフ
class Graph2d {
public:
    size_t n;
    vector<int> matrix;

    Graph2d(size_t size) :n(size), matrix(size*size) {};

    void resize(size_t s) {
        n = s;
        matrix.resize(n*n);
    }

    inline int& at(int y, int x) { return matrix[y*n + x]; }
    inline int& operator()(int y, int x) { return matrix[y*n + x]; }
    inline int at(int y, int x) const { return matrix[y*n + x]; }
    inline int operator()(int y, int x) const { return matrix[y*n + x]; }

    inline void connect(int u, int v, int dist = 1) {
        at(u, v) = at(v, u) = dist;
    }
    inline void connect_d(int u, int v, int dist = 1) { // directedEdge u->v
        at(u, v) = dist;
    }

};

void warshall_floyd(Graph2d& g) {
    int i, j, k;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++) {
            for (k = 0; k < g.n; k++) {
                g(j, k) = min(g(j, k), g(j, i) + g(i, k));
            }
        }
    }
}


int n, m;

int ss[100];

int main() {
    scanner >> n;

    repeat(n) {
        scanner >> ss[cnt];
    }

    scanner >> m;

    Graph2d graph(n);
    fill(ALL(graph.matrix), 98989898);

    int a, b, c;
    repeat(m) {
        scanner >> a >> b >> c;
        graph.connect(a, b, c);
    }

    warshall_floyd(graph);

    int result = 98989898;
    for (int u = 1; u < n - 1; ++u) {
        for (int v = 1; v < n - 1; ++v) {
            if (u == v) continue;
            result = min(result,
                graph(0, v) + graph(v, u) + graph(u, n - 1) + ss[v] + ss[u]
            );
        }
    }

    cout << result << endl;

    return 0;
}
0