Submission #352532
Source Code Expand
#include <iostream> #include <emmintrin.h> using namespace std; int N, M; int d[420][420] __attribute__((aligned(32))); int K; static inline __m128i _mm_min_epi32(__m128i a, __m128i b) { __asm__("pminsd %1, %0" : "+x"(a) : "xm"(b)); return a; } int main() { while (cin >> N >> M) { for (int i = 0; i <= 400; i++) { for (int j = 0; j <= 400; j++) { d[i][j] = 1<<28; } d[i][i] = 0; } for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; --a; --b; d[a][b] = d[b][a] = c; } // for (int k = 0; k < N; k++) { // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // } // } // } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { int j = 0; // ik = {d[i][k], d[i][k], d[i][k], d[i][k]} __m128i ik = _mm_set_epi32(d[i][k], d[i][k], d[i][k], d[i][k]); for (;j<N;j+=4) { // やること // d[i][j] に最小値をセットする // base = {d[i][j], d[i][j+1], d[i][j+2], d[i][j+3]} __m128i base = _mm_load_si128((__m128i*)(d[i] + j)); // fact = {d[k][j], d[k][j+1], d[k][j+2], d[k][j+3]} __m128i fact = _mm_load_si128((__m128i*)(d[k] + j)); fact = _mm_add_epi32(fact, ik); base = _mm_min_epi32(base, fact); _mm_store_si128((__m128i*)(d[i] + j), base); } for (;j<N;j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } cin >> K; while (K--) { int x, y, z; cin>>x>>y>>z; --x; --y; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][x] + z + d[y][j]); d[i][j] = min(d[i][j], d[i][y] + z + d[x][j]); } } long long s = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { s += d[i][j]; } } cout << s << endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - アットコーダー王国の交通事情 |
User | brly |
Language | C++11 (Clang++ 3.4) |
Score | 100 |
Code Size | 2257 Byte |
Status | AC |
Exec Time | 313 ms |
Memory | 1568 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 10 / 10 | 90 / 90 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt |
Subtask1 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_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 |
All | subtask0_sample_01.txt, subtask0_sample_02.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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 24 ms | 1380 KB |
subtask0_sample_02.txt | AC | 24 ms | 1396 KB |
subtask1_01.txt | AC | 24 ms | 1568 KB |
subtask1_02.txt | AC | 291 ms | 1444 KB |
subtask1_03.txt | AC | 293 ms | 1440 KB |
subtask1_04.txt | AC | 293 ms | 1568 KB |
subtask1_05.txt | AC | 293 ms | 1452 KB |
subtask1_06.txt | AC | 296 ms | 1444 KB |
subtask1_07.txt | AC | 295 ms | 1564 KB |
subtask1_08.txt | AC | 294 ms | 1560 KB |
subtask1_09.txt | AC | 296 ms | 1380 KB |
subtask1_10.txt | AC | 291 ms | 1560 KB |
subtask1_11.txt | AC | 291 ms | 1448 KB |
subtask1_12.txt | AC | 291 ms | 1568 KB |
subtask1_13.txt | AC | 291 ms | 1444 KB |
subtask1_14.txt | AC | 294 ms | 1560 KB |
subtask1_15.txt | AC | 295 ms | 1568 KB |
subtask1_16.txt | AC | 302 ms | 1556 KB |
subtask1_17.txt | AC | 300 ms | 1440 KB |
subtask1_18.txt | AC | 312 ms | 1564 KB |
subtask1_19.txt | AC | 302 ms | 1444 KB |
subtask1_20.txt | AC | 313 ms | 1440 KB |
subtask1_21.txt | AC | 301 ms | 1564 KB |
subtask1_22.txt | AC | 297 ms | 1568 KB |
subtask1_23.txt | AC | 295 ms | 1440 KB |
subtask1_24.txt | AC | 29 ms | 1556 KB |
subtask1_25.txt | AC | 33 ms | 1560 KB |
subtask1_26.txt | AC | 29 ms | 1560 KB |
subtask1_27.txt | AC | 32 ms | 1568 KB |
subtask1_28.txt | AC | 28 ms | 1440 KB |
subtask1_29.txt | AC | 25 ms | 1440 KB |