Submission #833026

#	Time	Username	Problem	Language	Result	Execution time	Memory
833026		Saacoota	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	167 ms	15984 KiB

commuter_pass

#include    <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b)  for(int i=(a);i<(b);++i)
#define fi  first
#define se  second
#define LL  unsigned long long
#define uint unsigned int
#define pb  push_back
#define eb  emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "commuter"
using   namespace   std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 5;
int n , m , topo[maxn] , tim ;
long long d[maxn][3] , dp[maxn] , res;
bool vs[maxn];
vector < ii > g[maxn];
vector < int > adj[maxn];
///--------------------------
void dijkstra(int u,int ty) {
    priority_queue < ii , vector < ii > , greater < ii > > pt;
    d[u][ty] = 0;
    pt.push({d[u][ty] , u});
    while (!pt.empty()) {
        ii x = pt.top();
        pt.pop();
        long long dis = x.fi;
        int u = x.se;
        if (dis != d[u][ty]) continue;
        for (auto v : g[u]) {
            if (d[v.fi][ty] > dis + v.se) {
                d[v.fi][ty] = dis + v.se;
                pt.push({d[v.fi][ty] , v.fi});
            }
        }
    }
}
///--------------------------
void DFS(int u) {
    vs[u] = true;
    topo[++tim] = u;
    for (auto v : adj[u])
    if (!vs[v]) DFS(v);
}
///--------------------------
void readf() {
    int s , t , u , v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1 ; i <= m ; ++i) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].eb(v , w);
        g[v].eb(u , w);
    }
    memset(d,inf,sizeof(d));
    memset(dp,inf,sizeof(dp));
    dijkstra(s,0);
    dijkstra(u,1);
    dijkstra(v,2);
    res = d[v][1];
}
///--------------------------
void solve() {
    for (int u = 1 ; u <= n ; ++u)
    for (auto v : g[u])
    if (d[u][0] + v.se == d[v.fi][0]) adj[u].pb(v.fi);
    DFS(1);
    for (int i = n ; i > 0 ; --i) {
        int u = topo[i];
        for (auto v : adj[u]) {
            dp[u] = min(dp[u] , dp[v]);
            dp[u] = min(dp[u] , d[u][2]);
        }
    }
    for (int u = 1 ; u <= n ; ++u) res = min(res , dp[u] + d[u][1]);
    memset(dp,inf,sizeof(dp));
    for (int i = n ; i > 0 ; --i) {
        int u = topo[i];
        for (auto v : adj[u]) {
            dp[u] = min(dp[u] , dp[v]);
            dp[u] = min(dp[u] , d[u][1]);
        }
    }
    for (int u = 1 ; u <= n ; ++u) res = min(res , dp[u] + d[u][2]);
    cout << res;
}
///--------------------------
int main() {
   #ifdef BDP0509
       freopen(TASK".inp", "r", stdin);
       freopen(TASK".out", "w", stdout);
   #endif // ONLINE_JUDGE
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void readf()':
commuter_pass.cpp:61:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   61 |     memset(d,inf,sizeof(d));
      |              ^~~
commuter_pass.cpp:62:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   62 |     memset(dp,inf,sizeof(dp));
      |               ^~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:82:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   82 |     memset(dp,inf,sizeof(dp));
      |               ^~~

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