oj.uz

Submission #65070

# Submission time Handle Problem Language Result Execution time Memory
65070 2018-08-06T14:31:29 Z patrikpavic2 Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 2000 ms 25176 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, ll> 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(cur.X + sus.Y < dis[sus.X][ind]){
                dis[sus.X][ind] = cur.X + sus.Y;
                ss.insert({cur.X + sus.Y, 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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &s, &t, &u, &vv);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:74:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x,y,c;scanf("%d%d%d", &x, &y, &c);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 22688 KB Output is correct
2 Execution timed out 2048 ms 22688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 25176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 25176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 22688 KB Output is correct
2 Execution timed out 2048 ms 22688 KB Time limit exceeded
3 Halted 0 ms 0 KB -