Submission #65077

#	Time	Username	Problem	Language	Result	Execution time	Memory
65077		patrikpavic2	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	909 ms	140884 KiB

commuter_pass

#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 (stderr)

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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45