# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
65068 | 2018-08-06T14:24:30 Z | patrikpavic2 | Commuter Pass (JOI18_commuter_pass) | C++17 | 2000 ms | 36120 KB |
#include <cstdio> #include <cstring> #include <set> #include <vector> #define X first #define Y second using namespace std; typedef long long ll; typedef pair < ll, int> pii; const int N = 1e5 + 500; const ll INF = 0x3f3f3f3f; set < pii > ss; vector < pii > v[N]; vector < int > g[N]; ll dis[N][4]; int n, m, s, t, u, vv; void dijkstra(int x,int ind){ for(int i = 1;i<=n;i++) dis[i][ind] = INF * INF; dis[x][ind] = 0; ss.insert({0, x}); while(!ss.empty()){ pii cur = *ss.begin(); ss.erase(ss.begin()); for(pii sus : v[cur.Y]){ if(sus.Y + cur.X < dis[sus.X][ind]){ dis[sus.X][ind] = sus.Y + cur.X; ss.insert({sus.Y + cur.X, sus.X}); } } } } void dijkstra_dag(){ for(int x = 1;x<=n;x++){ for(pii y : v[x]){ if(dis[x][0] + dis[y.X][1] + y.Y == dis[t][0]){ g[x].push_back(y.X); } } } } ll f(int x,int msk){ if(x == t){ if(msk == 0) return dis[x][2] + dis[x][3]; if(msk == 1) return dis[x][3]; if(msk == 2) return dis[x][2]; if(msk == 3) return 0; } ll ret = INF * INF; for(int y : g[x]){ ret = min(ret, f(y, msk)); ret = min(ret, f(y, msk | 1) + dis[x][2]); ret = min(ret, f(y, msk | 2) + dis[x][3]); ret = min(ret, f(y, msk | 3) + dis[x][2] + dis[x][3]); } return ret; } int main(){ scanf("%d%d", &n, &m); scanf("%d%d%d%d", &s, &t, &u, &vv); for(int i = 0;i<m;i++){ int x,y,c;scanf("%d%d%d", &x, &y, &c); v[x].push_back({y, c}); v[y].push_back({x, c}); } dijkstra(s, 0); dijkstra(t, 1); dijkstra(u, 2); dijkstra(vv, 3); //printf("%lld\n", dis[t][0]); // printf("%lld\n", dis[s][1]); dijkstra_dag(); printf("%lld\n", min(f(s, 0), dis[u][3])); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1083 ms | 26648 KB | Output is correct |
2 | Execution timed out | 2058 ms | 29628 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2073 ms | 36120 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2069 ms | 36120 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1083 ms | 26648 KB | Output is correct |
2 | Execution timed out | 2058 ms | 29628 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |