Submission #42109

#	Time	Username	Problem	Language	Result	Execution time	Memory
42109		nonocut	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2052 ms	15108 KiB

commuter_pass

#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;
ll da[maxn], db[maxn], dc[maxn], dd[maxn];
pair<ll,ll> mn[maxn];
vector<pair<int,ll>> way[maxn];
ll ans;
void ssspt(int u, ll* dist) {
    priority_queue<node> heap;
    for(int i=1;i<=n;i++) dist[i] = inf;
    dist[u] = 0;
    heap.push(node(u,0));
    while(!heap.empty()) {
        auto t = heap.top(); heap.pop();
        u = t.x;
        if(dist[u]<t.val) continue;
        for(auto nxt : way[u]) {
            int v = nxt.X; ll val = nxt.Y;
            if(dist[v] > dist[u]+val) {
                dist[v] = dist[u]+val;
                heap.push(v);
            }
        }
    }
}
void sssp(int u, ll* dist) {
    priority_queue<node> heap;
    for(int i=1;i<=n;i++) {
        dist[i] = inf;
        mn[i] = {dc[i], dd[i]};
    }
    dist[u] = 0;
    heap.push(node(u,0));
    while(!heap.empty()) {
        auto t = heap.top(); heap.pop();
        u = t.x;
        if(dist[u]<t.val) continue;
        if(dist[u]+db[u]==db[a]) {
//            printf("u = %d : %lld + %lld or %lld + %lld\n",u,mn[u].X,dd[u],mn[u].Y,dc[u]);
            ans = min(ans, mn[u].X + dd[u]);
            ans = min(ans, mn[u].Y + dc[u]);
        }
        for(auto nxt : way[u]) {
            int v = nxt.X; ll val = nxt.Y;
            if(dist[v] > dist[u]+val) {
                dist[v] = dist[u]+val;
                heap.push(v);
            }
            if(dist[v] == dist[u]+val) {
                mn[v].X = min(mn[v].X,mn[u].X);
                mn[v].Y = min(mn[v].Y,mn[u].Y);
            }
        }
    }
}
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});
    }
    ssspt(b,db);
    ssspt(c,dc);
    ssspt(d,dd);

    ans = dd[c];
    sssp(a,da);
//    for(int i=1;i<=n;i++) {
//        printf("%d\n",i);
//        printf("--- dist from a = %lld\n",da[i]);
//        printf("--- dist from b = %lld\n",db[i]);
//        printf("--- dist from c = %lld\n",dc[i]);
//        printf("--- dist from d = %lld\n",dd[i]);
//    }
    printf("%lld",ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:24: 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:74:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&a,&b,&c,&d);
                                  ^
commuter_pass.cpp:77:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld",&x,&y,&val);
                                     ^

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45