Submission #833039

#	Time	Username	Problem	Language	Result	Execution time	Memory
833039		Saacoota	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	283 ms	26680 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 <long long , 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 , tim , s , t;
long long d[maxn][4] , dp[maxn] , res , ans;
ii a[maxn];
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 readf() {
    int 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);
    dijkstra(t,3);
    ans = res = d[v][1];
}
///--------------------------
bool in(int u) {
    return (d[u][0] + d[u][3] == d[t][0]);
}
///--------------------------
void solve() {
    for (int i = 1 ; i <= n ; ++i) a[i] = ii(d[i][0] , i);
    sort(a + 1 , a + n + 1);

    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) dp[u] = d[u][2];
    for (int i = n ; i > 0 ; --i) {
        int u = a[i].se;
        if (!in(u)) continue;
        for (auto v : g[u])
        if (in(v.fi) && d[v.fi][0] == d[u][0] + v.se) {
            dp[u] = min(dp[u] , dp[v.fi]);
        }
    }
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) res = min(res , dp[u] + d[u][1]);

    memset(dp,inf,sizeof(dp));
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) dp[u] = d[u][1];
    for (int i = n ; i > 0 ; --i) {
        int u = a[i].se;
        if (!in(u)) continue;
        for (auto v : g[u])
        if (in(v.fi) && d[v.fi][0] == d[u][0] + v.se) {
            dp[u] = min(dp[u] , dp[v.fi]);
        }
    }
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) res = min(res , dp[u] + d[u][2]);
    cout << res << '\n';
}
///--------------------------
void solve1() {
    for (int u = 1 ; u <= n ; ++u)
    for (int v = 1 ; v <= n ; ++v)
    if (in(u) && in(v)) ans = min(ans , d[u][1] + d[v][2]);
    cout << ans << '\n';
}
///--------------------------
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();
   //solve1();
}

Compilation message (stderr)

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

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