Submission #1072217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072217		HNa_seawjing	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	370 ms	16600 KiB

commuter_pass

#include <bits/stdc++.h>
//code
#define fl(i,x,y,z) for(int i=x;i<=y;i=i+z)
#define fn(i,x,y,z) for(int i=x;i>=y;i=i-z)
#define rep(i,x,y) for(int i=x;i<y;i=i+1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define tle cout<<"tle"<<endl
#define edl cout<<"\n"
#define el "\n"
#define getbit(x,i) ((x>>i)&1)
#define bitcnt __builtin_popcount
//ham
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=1e5+5;
const ll mod=1e9+7;
int n,m;
int u,v,s,t;
vector <pii> e[N];
int ds[N],dt[N],du[N],dv[N];
int f1[N],f2[N];
void inp()
{
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    fl(i,1,m,1)
    {
        int x,y,c; cin>>x>>y>>c;
        e[x].pb({y,c});
        e[y].pb({x,c});
    }
}
void dij(int p,int d[])
{
//    fl(i,1,n,1) d[i]=1e9;
//    d[p]=0;
//    priority_queue <pii,vector <pii>,greater<pii>> q;
//    q.push({d[p],p});
//    while (!q.empty())
//    {
//        int x=q.top().se;
//        int c=q.top().fi;
//        q.pop();
//        if (c>d[x]) continue;
//        for (auto it: e[x])
//        {
//            int y=it.fi,w=it.se;
//            if (d[y]>d[x]+w)
//            {
//                d[y]=d[x]+w;
//                q.push({d[y],y});
//            }
//        }
//    }
    for(int i=0; i<=n; i++) d[i] = 1e18;
    d[p] = 0;
    priority_queue<pii> Q;
    Q.push({0, p});
    while(Q.size()){
        int du, u;
        tie(du, u) = Q.top();
        Q.pop();
        du = -du;
        if(du != d[u]) continue;
        for(pii edge: e[u]){
            int v, c;
            tie(v, c) = edge;
            if(d[v] > du + c){
                d[v] = du + c;
                Q.push({-d[v], v});
            }
        }
    }
}

void sol()
{
    dij(s, ds);
    dij(t, dt);
    dij(u, du);
    dij(v, dv);
    vector<int> vt(n);
    for(int i=0; i<n; i++) vt[i] = i + 1;
    sort(vt.begin(), vt.end(), [&](const int &a, const int &b) -> bool {return ds[a] < ds[b];});


    memset(f1, 0x3f, sizeof f1);
    memset(f2, 0x3f, sizeof f2);

    int ans = du[v];
    for(int u: vt) if(ds[u] + dt[u] == ds[t]){
        f1[u] = du[u];
        f2[u] = dv[u];
        for(pii edge: e[u]){
            int v, c;
            tie(v, c) = edge;
            if(ds[v] + c == ds[u]){
                f1[u] = min(f1[v], f1[u]);
                f2[u] = min(f2[v], f2[u]);
            }
        }
        ans = min({ans, f1[u] + dv[u], f2[u] + du[u]});
    }
    cout<<ans;
}
signed main()
{
//    freopen("task.inp","r",stdin);
//    freopen("task.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    sol();
    return 0;
}
/*   /\_/\
    ( ._. )
    / >v< \
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(int, int*)':
commuter_pass.cpp:63:36: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   63 |     for(int i=0; i<=n; i++) d[i] = 1e18;
      |                                    ^~~~

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