Submission #352743
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++)
{
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++)
{
int j = 0;
__m128i ix = _mm_set_epi32(d[i][x]+z, d[i][x]+z, d[i][x]+z, d[i][x]+z);
__m128i iy = _mm_set_epi32(d[i][y]+z, d[i][y]+z, d[i][y]+z, d[i][y]+z);
for (;j<N;j+=4)
{
__m128i ij = _mm_load_si128((__m128i*)(d[i] + j));
__m128i yj = _mm_load_si128((__m128i*)(d[y] + j));
__m128i xj = _mm_load_si128((__m128i*)(d[x] + j));
__m128i l0 = _mm_add_epi32(ix, yj);
__m128i l1 = _mm_add_epi32(iy, xj);
ij = _mm_min_epi32(ij, l0);
ij = _mm_min_epi32(ij, l1);
_mm_store_si128((__m128i*)(d[i] + j), ij);
}
// 端数処理必要なし
}
long long s = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
s += d[i][j];
// {
// __m128i zero = _mm_setzero_si128();
// for (int i = 0; i < N; i++)
// {
// int j = i+1;
//
// __m128i sum = _mm_setzero_si128();
// for (;(j+8)<N;j+=8)
// {
// __m128i l0 = _mm_load_si128((__m128i*)(d[i] + j));
// __m128i l1 = _mm_load_si128((__m128i*)(d[i] + j + 4));
// __m128i s = _mm_hadd_epi32(l0, l1);
// sum = _mm_hadd_epi32(sum, s);
// }
// // 64bit 対応しないといけないので面倒くさくなった..
//
// for (;j<N;j++)
// {
// s += d[i][j];
// }
// }
// }
cout << s << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - アットコーダー王国の交通事情 |
User |
brly |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
3211 Byte |
Status |
AC |
Exec Time |
151 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 |
1564 KB |
subtask0_sample_02.txt |
AC |
24 ms |
1432 KB |
subtask1_01.txt |
AC |
28 ms |
1556 KB |
subtask1_02.txt |
AC |
148 ms |
1568 KB |
subtask1_03.txt |
AC |
150 ms |
1396 KB |
subtask1_04.txt |
AC |
147 ms |
1436 KB |
subtask1_05.txt |
AC |
151 ms |
1436 KB |
subtask1_06.txt |
AC |
150 ms |
1564 KB |
subtask1_07.txt |
AC |
149 ms |
1564 KB |
subtask1_08.txt |
AC |
151 ms |
1560 KB |
subtask1_09.txt |
AC |
150 ms |
1568 KB |
subtask1_10.txt |
AC |
149 ms |
1444 KB |
subtask1_11.txt |
AC |
147 ms |
1448 KB |
subtask1_12.txt |
AC |
149 ms |
1440 KB |
subtask1_13.txt |
AC |
150 ms |
1364 KB |
subtask1_14.txt |
AC |
150 ms |
1568 KB |
subtask1_15.txt |
AC |
150 ms |
1376 KB |
subtask1_16.txt |
AC |
149 ms |
1448 KB |
subtask1_17.txt |
AC |
149 ms |
1564 KB |
subtask1_18.txt |
AC |
150 ms |
1372 KB |
subtask1_19.txt |
AC |
149 ms |
1444 KB |
subtask1_20.txt |
AC |
151 ms |
1436 KB |
subtask1_21.txt |
AC |
148 ms |
1568 KB |
subtask1_22.txt |
AC |
150 ms |
1564 KB |
subtask1_23.txt |
AC |
148 ms |
1436 KB |
subtask1_24.txt |
AC |
29 ms |
1440 KB |
subtask1_25.txt |
AC |
28 ms |
1440 KB |
subtask1_26.txt |
AC |
30 ms |
1440 KB |
subtask1_27.txt |
AC |
30 ms |
1452 KB |
subtask1_28.txt |
AC |
27 ms |
1568 KB |
subtask1_29.txt |
AC |
28 ms |
1448 KB |