Submission #259311

#	Time	Username	Problem	Language	Result	Execution time	Memory
259311		Fidisk	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2086 ms	32384 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;

const ld pi=acos(-1);

struct comp{
    bool operator() (pll x,pll y) {
        return x.se>y.se;
    }
};

ll n,m,s,t,u,v,a,b,c,res,f[5][500009],i;
priority_queue<pll,vector<pll>,comp> heap;
vector<pll> g[500009];
pll tmp;

void Dijsktra(ll x,ll y){
    heap.push({y,y-y});
    for (int ii=1;ii<=n;ii++) {
        f[x][ii]=oo;
    }
    f[x][y]=0;
    while (!heap.empty()) {
        tmp=heap.top();
        heap.pop();
        if (f[x][tmp.fi]<tmp.se) {
            
        } 
        else {
            for (int ii=0;ii<g[tmp.fi].size();ii++) {
                if (f[x][g[tmp.fi][ii].fi]>tmp.se+g[tmp.fi][ii].se) {
                    f[x][g[tmp.fi][ii].fi]=tmp.se+g[tmp.fi][ii].se;
                    heap.push({g[tmp.fi][ii].fi,tmp.se+g[tmp.fi][ii].se});
                }
            }
        }
    }
}

pll calc(pll x,pll y) {
    return {min(x.fi,y.fi),min(x.se,y.se)};
}

pll Trace(ll x) {
    //cout<<x<<'\n';
    pll kq={f[2][x],f[3][x]};
    for (int ii=0;ii<g[x].size();ii++) {
        if ((f[1][g[x][ii].fi]==f[1][x]-g[x][ii].se)) {
            pll tmp3=Trace(g[x][ii].fi);
            kq=calc(kq,tmp3);
        }
    }
    return kq;
}

int main(){
    IO;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for (i=1;i<=m;i++) {
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    Dijsktra(1,s);
    Dijsktra(2,u);
    Dijsktra(3,v);
    res=f[2][v];
    pll tmp2=Trace(t);
    //cout<<tmp2.fi<<' '<<tmp2.se<<'\n';
    res=min(tmp2.fi+tmp2.se,res);
    cout<<res;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijsktra(ll, ll)':
commuter_pass.cpp:51:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int ii=0;ii<g[tmp.fi].size();ii++) {
                           ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'pll Trace(ll)':
commuter_pass.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii=0;ii<g[x].size();ii++) {
                   ~~^~~~~~~~~~~~

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