# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
42106 | 2018-02-22T15:47:55 Z | nonocut | Commuter Pass (JOI18_commuter_pass) | C++14 | 73 ms | 1388 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 305; const ll inf = 1e18; int n,m,a,b,c,d; ll dist[maxn][maxn]; int main() { int i,x,y,z; ll val; scanf("%d%d",&n,&m); if(n>300) return 0; scanf("%d%d%d%d",&a,&b,&c,&d); for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { if(x==y) dist[x][y] = 0; else dist[x][y] = inf; } } for(i=0;i<m;i++) { scanf("%d%d%lld",&x,&y,&val); dist[x][y] = min(dist[x][y], val); dist[y][x] = min(dist[y][x], val); } for(z=1;z<=n;z++) { for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]); } } } ll ans = dist[c][d]; for(x=1;x<=n;x++) { for(y=1;y<=n;y++) { if(dist[a][x] + dist[x][y] + dist[y][b] != dist[a][b]) continue; // printf("x = %d y = %d (%lld or %lld)\n",x,y,dist[x][c] + dist[y][d],dist[x][d] + dist[y][c]); ans = min(ans, dist[x][c] + dist[y][d]); ans = min(ans, dist[x][d] + dist[y][c]); } } printf("%lld",ans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 1196 KB | Output is correct |
2 | Correct | 36 ms | 1196 KB | Output is correct |
3 | Correct | 38 ms | 1196 KB | Output is correct |
4 | Correct | 73 ms | 1196 KB | Output is correct |
5 | Correct | 45 ms | 1324 KB | Output is correct |
6 | Correct | 35 ms | 1324 KB | Output is correct |
7 | Correct | 37 ms | 1328 KB | Output is correct |
8 | Correct | 40 ms | 1328 KB | Output is correct |
9 | Correct | 35 ms | 1328 KB | Output is correct |
10 | Correct | 49 ms | 1328 KB | Output is correct |
11 | Correct | 39 ms | 1328 KB | Output is correct |
12 | Correct | 36 ms | 1328 KB | Output is correct |
13 | Correct | 36 ms | 1328 KB | Output is correct |
14 | Correct | 37 ms | 1328 KB | Output is correct |
15 | Correct | 37 ms | 1388 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |