# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
42111 | 2018-02-22T16:28:58 Z | nonocut | Commuter Pass (JOI18_commuter_pass) | C++14 | 474 ms | 18444 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define X first #define Y second const int maxn = 100005; const ll inf = 1e18; struct node { int x; ll val; node(int _x = 0, ll _val = 0) { x = _x; val = _val; }; bool operator < (node a) const { return a.val<val; } }; int n,m,a,b,c,d; bool vis[maxn]; ll dist[maxn], da[maxn], db[maxn], dc[maxn], dd[maxn]; vector<pair<int,ll>> way[maxn]; priority_queue<node> heap; ll ans; void sssp(int u) { for(int i=1;i<=n;i++) dist[i] = inf, vis[i] = 0; dist[u] = 0; heap.push(node(u,0)); while(!heap.empty()) { int u = heap.top().x; heap.pop(); if(vis[u]) continue; vis[u] = 1; for(auto t : way[u]) { if(dist[t.X] > dist[u] + t.Y) { dist[t.X] = dist[u] + t.Y; heap.push(node(t.X,dist[t.X])); } } } } int main() { scanf("%d%d",&n,&m); scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=0;i<m;i++) { int x,y; ll val; scanf("%d%d%lld",&x,&y,&val); way[x].pb({y,val}); way[y].pb({x,val}); } sssp(a); for(int i=1;i<=n;i++) da[i] = dist[i]; sssp(b); for(int i=1;i<=n;i++) db[i] = dist[i]; sssp(c); for(int i=1;i<=n;i++) dc[i] = dist[i]; sssp(d); for(int i=1;i<=n;i++) dd[i] = dist[i]; printf("%lld",ans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 451 ms | 18444 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 474 ms | 18444 KB | Output is correct |
2 | Incorrect | 454 ms | 18444 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 18444 KB | Output is correct |
2 | Incorrect | 4 ms | 18444 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 451 ms | 18444 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |