oj.uz

Submission #65077

# Submission time Handle Problem Language Result Execution time Memory
65077 2018-08-06T14:41:50 Z patrikpavic2 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 909 ms 140884 KB 
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <cstring>
#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;

priority_queue < pii > ss;
vector < pii > v[N];
vector < int > g[N];
ll dis[N][4], dp[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.push({0, x});
    while(!ss.empty()){
        pii cur = ss.top();
        cur.X *= -1LL;
        ss.pop();
        for(pii sus : v[cur.Y]){
            if(cur.X + sus.Y < dis[sus.X][ind]){
                dis[sus.X][ind] = cur.X + sus.Y;
                ss.push({- 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]){
                //printf("EDGE %d -> %d\n", x, y);
                g[x].push_back(y.X);
            }
        }
    }
}

ll f(int x,int msk){
    if(dp[x][msk] != -1) return dp[x][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 dp[x][msk] = ret;
}

int main(){
    memset(dp, -1, sizeof(dp));
    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();
    //return 0;
    printf("%lld\n", min(f(s, 0), dis[u][3]));
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:77: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:78: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:80: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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 23920 KB Output is correct
2 Correct 647 ms 23920 KB Output is correct
3 Correct 758 ms 34384 KB Output is correct
4 Correct 616 ms 34384 KB Output is correct
5 Correct 844 ms 34864 KB Output is correct
6 Correct 696 ms 39072 KB Output is correct
7 Correct 798 ms 42756 KB Output is correct
8 Correct 742 ms 46088 KB Output is correct
9 Correct 676 ms 49484 KB Output is correct
10 Correct 574 ms 53800 KB Output is correct
11 Correct 353 ms 54648 KB Output is correct
12 Correct 646 ms 60144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 62880 KB Output is correct
2 Correct 844 ms 66956 KB Output is correct
3 Correct 881 ms 69452 KB Output is correct
4 Correct 815 ms 73504 KB Output is correct
5 Correct 909 ms 77848 KB Output is correct
6 Correct 872 ms 84540 KB Output is correct
7 Correct 861 ms 88536 KB Output is correct
8 Correct 869 ms 88536 KB Output is correct
9 Correct 880 ms 91868 KB Output is correct
10 Correct 891 ms 94196 KB Output is correct
11 Correct 391 ms 94852 KB Output is correct
12 Correct 732 ms 104736 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 104736 KB Output is correct
2 Correct 11 ms 104736 KB Output is correct
3 Correct 10 ms 104736 KB Output is correct
4 Correct 35 ms 104736 KB Output is correct
5 Correct 23 ms 104736 KB Output is correct
6 Correct 12 ms 104736 KB Output is correct
7 Correct 12 ms 104736 KB Output is correct
8 Correct 13 ms 104736 KB Output is correct
9 Correct 12 ms 104736 KB Output is correct
10 Correct 28 ms 104736 KB Output is correct
11 Correct 13 ms 104736 KB Output is correct
12 Correct 12 ms 104736 KB Output is correct
13 Correct 12 ms 104736 KB Output is correct
14 Correct 11 ms 104736 KB Output is correct
15 Correct 13 ms 104736 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 23920 KB Output is correct
2 Correct 647 ms 23920 KB Output is correct
3 Correct 758 ms 34384 KB Output is correct
4 Correct 616 ms 34384 KB Output is correct
5 Correct 844 ms 34864 KB Output is correct
6 Correct 696 ms 39072 KB Output is correct
7 Correct 798 ms 42756 KB Output is correct
8 Correct 742 ms 46088 KB Output is correct
9 Correct 676 ms 49484 KB Output is correct
10 Correct 574 ms 53800 KB Output is correct
11 Correct 353 ms 54648 KB Output is correct
12 Correct 646 ms 60144 KB Output is correct
13 Correct 779 ms 62880 KB Output is correct
14 Correct 844 ms 66956 KB Output is correct
15 Correct 881 ms 69452 KB Output is correct
16 Correct 815 ms 73504 KB Output is correct
17 Correct 909 ms 77848 KB Output is correct
18 Correct 872 ms 84540 KB Output is correct
19 Correct 861 ms 88536 KB Output is correct
20 Correct 869 ms 88536 KB Output is correct
21 Correct 880 ms 91868 KB Output is correct
22 Correct 891 ms 94196 KB Output is correct
23 Correct 391 ms 94852 KB Output is correct
24 Correct 732 ms 104736 KB Output is correct
25 Correct 22 ms 104736 KB Output is correct
26 Correct 11 ms 104736 KB Output is correct
27 Correct 10 ms 104736 KB Output is correct
28 Correct 35 ms 104736 KB Output is correct
29 Correct 23 ms 104736 KB Output is correct
30 Correct 12 ms 104736 KB Output is correct
31 Correct 12 ms 104736 KB Output is correct
32 Correct 13 ms 104736 KB Output is correct
33 Correct 12 ms 104736 KB Output is correct
34 Correct 28 ms 104736 KB Output is correct
35 Correct 13 ms 104736 KB Output is correct
36 Correct 12 ms 104736 KB Output is correct
37 Correct 12 ms 104736 KB Output is correct
38 Correct 11 ms 104736 KB Output is correct
39 Correct 13 ms 104736 KB Output is correct
40 Correct 655 ms 104736 KB Output is correct
41 Correct 587 ms 107592 KB Output is correct
42 Correct 621 ms 111960 KB Output is correct
43 Correct 454 ms 115404 KB Output is correct
44 Correct 418 ms 117440 KB Output is correct
45 Correct 681 ms 121704 KB Output is correct
46 Correct 771 ms 124844 KB Output is correct
47 Correct 660 ms 127700 KB Output is correct
48 Correct 440 ms 127700 KB Output is correct
49 Correct 598 ms 133032 KB Output is correct
50 Correct 730 ms 136796 KB Output is correct
51 Correct 634 ms 140884 KB Output is correct