Submission #1264128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264128		bnd2100	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2094 ms	46568 KiB

commuter_pass

/*
        /$$$$$$                                  /$$                            
        /$$__  $$                                | $$                            
        | $$  \__/  /$$$$$$   /$$$$$$   /$$$$$$  /$$$$$$    /$$$$$$   /$$$$$$  /$$
        | $$       /$$__  $$ /$$__  $$ |____  $$|_  $$_/   /$$__  $$ /$$__  $$|__/
        | $$      | $$  \__/| $$$$$$$$  /$$$$$$$  | $$    | $$  \ $$| $$  \__/    
        | $$    $$| $$      | $$_____/ /$$__  $$  | $$ /$$| $$  | $$| $$       /$$
        |  $$$$$$/| $$      |  $$$$$$$|  $$$$$$$  |  $$$$/|  $$$$$$/| $$      |__/
        \______/ |__/       \_______/ \_______/   \___/   \______/ |__/          
                                                                                
                                                                                
                                                                                
                    /$$   /$$                                                    
                    | $$$ | $$                                                    
                    | $$$$| $$  /$$$$$$  /$$   /$$ /$$   /$$  /$$$$$$  /$$$$$$$   
                    | $$ $$ $$ /$$__  $$| $$  | $$| $$  | $$ /$$__  $$| $$__  $$  
                    | $$  $$$$| $$  \ $$| $$  | $$| $$  | $$| $$$$$$$$| $$  \ $$  
                    | $$\  $$$| $$  | $$| $$  | $$| $$  | $$| $$_____/| $$  | $$  
                    | $$ \  $$|  $$$$$$$|  $$$$$$/|  $$$$$$$|  $$$$$$$| $$  | $$  
                    |__/  \__/ \____  $$ \______/  \____  $$ \_______/|__/  |__/  
                            /$$  \ $$           /$$  | $$                      
                            |  $$$$$$/          |  $$$$$$/                      
                            \______/            \______/                       


* @Author: Nguyn
* @Last Modified by: Nguyn
*/

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

// ------------ Define ------------

#define el "\n"
#define int long long
#define ld long double
#define str string
#define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
#define IOS {std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define _TBN_ signed main()
#define setp(n) setprecision(n)<< fixed
#define fi first
#define se second
#define ii pair<int,int>
#define gcd(a,b) __gcd(a,b)
#define tup pair<int,ii>
#define pb push_back
#define pf push_front

const int maxn = 1e6+9;
const long long oo = 1e18;
const int MOD = 1e9+7, Mod = 111539786;
const int base = 311;

void sub1();
void sub2();
void sub3();

void Try(int pos, int prev1, int prev2);

int lcm(int a, int b)
{
    return a/gcd(a,b)*b;
}

int sqr(int x) {return x*x;}

inline bool MASK(int mask, int bit) {return ((mask>>bit)&1);}
long long F(int n) {return n*(n+1)/2;}
inline int Sum(int a, int b, int m) {return (a%m+b%m)%m;}
inline int Sub(int a, int b, int m) {return (a%m-b%m+m)%m;}
inline int Mul(int a, int b, int m) {return ((a%m)*(b%m))%m;}

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int n,m,S,T,U,V;
vector<ii> adj[maxn];
int dis[4][maxn];
bool vis[maxn];
void dijk(int st, int type)
{
    priority_queue<ii,vector<ii>,greater<ii>> q;
    fill(dis[type]+1,dis[type]+1+n,oo);
    fill(vis+1,vis+1+n,0);
    dis[type][st] = 0;
    q.push({0,st});
    while(!q.empty())
    {
        int u = q.top().se;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for(ii cur : adj[u])
        {
            int v = cur.fi, w = cur.se;
            if (dis[type][v]>dis[type][u]+w)
            {
                dis[type][v] = dis[type][u]+w;
                q.push({dis[type][v],v});
            }
        }
    }
}

int best[2][maxn],ans;
void dfs(int u, int ed)
{
    best[0][u] = dis[2][u];
    best[1][u] = dis[3][u];
    if (u==ed) return;
    for(ii cur : adj[u])
    {
        int v = cur.fi, w = cur.se;
        if (dis[0][u]+dis[1][v]+w!=dis[0][T]) continue;
        dfs(v,ed);
        best[0][u] = min(best[0][u],best[0][v]);
        best[1][u] = min(best[1][u],best[1][v]);
    }
    ans = min(ans,best[0][u]+dis[3][u]);
    ans = min(ans,dis[2][u]+best[1][u]);
}

_TBN_
{
    IOS;
    if (fopen("bus.inp","r")) file("bus");
    cin >>n >>m >>S >>T >>U >>V;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin >>u >>v >>c;
        adj[u].pb({v,c});
        adj[v].pb({u,c});
    }
    for(int i=1;i<=1;i++)
    {
        sub1();
    }
    return 0;
}

void sub1()
{
    dijk(S,0);
    dijk(T,1);
    dijk(U,2);
    dijk(V,3);
    dfs(S,T);
    ans = dis[2][V];
    dfs(S,T);
    cout<< ans<< el;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:39:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 | #define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:128:31: note: in expansion of macro 'file'
  128 |     if (fopen("bus.inp","r")) file("bus");
      |                               ^~~~
commuter_pass.cpp:39:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 | #define file(name) {freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:128:31: note: in expansion of macro 'file'
  128 |     if (fopen("bus.inp","r")) file("bus");
      |                               ^~~~

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